题目描述

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

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

好巧，今天是游乐园一周年庆典，全场不限次数买一送一，也就是说若游玩一次费用为 $c_i$ 的设施，可以免费一次游玩 $c_j\ (c_j \leq c_i)$ 的设施。

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

输入格式

第一行包含三个正整数 $n,k,q \ (1\leq n,k,q \leq 500)$，分别表示游乐设施的数量、阿兔身上携带的钱，以及兔儿子指定要玩的游乐设施编号。

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

输出格式

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

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

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

-1

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

3