What is for dinner?

题面翻译

题面描述

鲨鱼有 $n$ 颗牙齿，分别分布于 $m$ 行上，第 $i$ 颗牙齿有一个初始活力值 $c_i$。鲨鱼有 $k$ 个食物想要吃，但是，每吃掉一个食物就要消耗某一排牙齿的每一颗牙齿各 $1$ 点活力，而鲨鱼必须保证每个牙齿的剩余活力不能到负数。 试求鲨鱼最多能吃到的食物个数。

输入格式

第一排三个整数 $n,m,k$，后面 $n$ 排每行两个整数 $x$ 和 $c_i$,分别表示这个牙齿所在的行数和初始活力值。

输出格式

输出一个整数，为答案。

数据范围与约定

• $1 \leq m \leq n \leq 1000$；
• $0 \leq k \leq 10^6$；
• $1 \leq x \leq m$；
• $0 \leq c_i \leq 10^6$。

样例 #1

样例输入 #1

4 3 18
2 3
1 2
3 6
2 3

样例输出 #1

11

样例 #2

样例输入 #2

2 2 13
1 13
2 12

样例输出 #2

13