题目描述

阿兔带着兔儿子一起去游乐园，那里有 $n$ 个游乐设施，每个设施的编号从 $1$ ~ $n$ 依次排列。

每个游乐设施在首次游玩时会提供 $h_i$ 的快乐值，后续游玩不再会获得快乐值。每次游玩都需要支付 的费用。而兔儿子坚持道：“我就要玩第 $i$ 个游乐设施，不答应我就呜呜呜！”

由于阿兔囊中羞涩，身上只有 $k$ 元，他需要在满足兔儿子要求的前提下，尽可能获得更多的快乐值。请问他最多可以得到多少快乐值？

输入格式

第一行包含三个正整数 $n,k,q \ (1\leq n,k,q \leq 2*10^{3})$，分别表示游乐设施的数量、阿兔身上携带的钱，以及询问的总数。

接下来的 $n$ 行，每行包含两个整数 $h_{i},c_{i} \ (1\leq h_{i},c_{i} \leq 10^{9})$，分别表示编号为 $i$ 的游乐设施提供的快乐值和游玩一次的花费。

最后一行包含 $q$ 个整数，表示每组询问中兔儿子指定要玩的游乐设施编号（每组询问彼此独立）。

输出格式

共输出 $q$ 行，每组询问对应一行结果。

对于每组询问，输出一个整数，表示阿兔在满足兔儿子的要求下最多能获得的快乐值。

如果阿兔的钱不足以满足兔儿子的要求，则输出 $-1$。

5 5 5
1 2
2 3
1 4
6 6
2 2
1 2 3 4 5

3
4
1
-1
4

解释 #1

对于第三组询问，兔儿子要求玩编号为 $3$ 的游乐设施。阿兔满足了兔儿子的要求后，剩余的钱不足以游玩其他设施，因此最多的快乐值就是编号为 $3$ 的游乐设施提供的快乐值。

对于第四组询问，兔儿子要求玩编号为 $4$ 的游乐设施。阿兔的钱不足以支付编号为 $4$ 的游乐设施的费用，无法满足兔儿子的要求，结果为 $-1$。