Cargas de um trecho

Time limit: 3000 msMemory limit: 256 MB

Há $n$ caixas em uma fila. A caixa $i$ tem peso $w_i$ e valor $v_i$ . Cada consulta fornece $l,r,c$ : escolha qualquer subconjunto das caixas de posições $l$ até $r$ , usando cada caixa no máximo uma vez, com peso total no máximo $c$ , e maximize o valor total. Escolher nenhuma caixa é permitido. As consultas são independentes.

Input

A primeira linha contém $n,q,W$ . Seguem $n$ linhas com $w_i,v_i$ e depois linhas com .

Output

Para cada consulta, imprima o maior valor possível.

Samples

Sample 1

Input

Output

7
5
0

Na primeira consulta, escolha as caixas 1 e 3.