Problem Statement

There are $N$ items numbered from $1$ to $N$. The weight of item $i$ is $W_i$ and the value is $V_i$.

You are given $Q$ queries, so process them in order. The $j$-th query is as follows:

• Integers $L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N)$ are given. When choosing some (possibly zero) items from items $L_j,L_j+1,\dots,R_j$ such that the total weight does not exceed $C_j$, find the maximum possible total value of the chosen items.

Constraints

• $1\leq N \leq 2\times 10^4$
• $1\leq Q \leq 2\times 10^5$
• $1\leq W_i \leq 500$
• $1\leq V_i \leq 10^9$
• $1\leq L_j \leq R_j \leq N$
• $1\leq C_j \leq 500$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
W_1 V_1
W_2 V_2
\vdots
W_N V_N
Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q

Output

Output $Q$ lines. The $i$-th line $(1\leq i \leq Q)$ should contain the answer for the $i$-th query.