Little T has $n$ items, where the $i$-th item has color $c_i$ and weight $a_i$.

Little T has $m$ backpacks. The $i$-th backpack must contain at least $l_i$ items and at most $r_i$ items, and all items in the $i$-th backpack must have color $i$.

The weight of a valid configuration is the sum of the weights of all items placed in the backpacks.

Find the weights of the $k$ smallest valid configurations. Two configurations are considered different if and only if there exists an item that is placed in a backpack in one configuration but not in the other.

Input

The first line contains three integers $n, m, k$, representing the number of items, the number of backpacks, and the number of smallest configurations to find.

The next $n$ lines each contain two integers $c_i, a_i$, representing the color and weight of the $i$-th item.

The next $m$ lines each contain two integers $l_i, r_i$, representing the lower and upper capacity limits of the backpacks.

Output

Output $k$ lines. The $i$-th line should contain an integer representing the $i$-th smallest weight. If the number of valid configurations is less than $i$, output $-1$.

Examples

Input 1

6 3 7
1 3
1 1
2 5
3 2
1 1
2 3
2 5
1 1
0 1

Output 1

5
7
7
7
7
8
9

Input 2

6 2 6
2 1
2 2
2 3
1 1
1 1
1 1
3 3
0 1

Output 2

3
4
5
6
-1
-1

Constraints

For all data, $1\leq n, m, k\leq 2\times 10^5$, $1\leq c_i\leq m$, $1\leq a_i\leq 10^9$, $0\leq l_i\leq r_i\leq n$.

Subtask 1 (15 points): $n, m, k\leq 4000$, $l_i=r_i=1$.

Subtask 2 (17 points): $n, m, a_i\leq 4000$, $l_i=r_i=1$.

Subtask 3 (25 points): $l_i=r_i=1$.

Subtask 4 (18 points): $l_i=0$.

Subtask 5 (25 points): No special restrictions.