题目描述

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

输入格式

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

输出格式

输出一个整数，为答案。

4 3 18
2 3
1 2
3 6
2 3

11

2 2 13
1 13
2 12

13

数据范围/提示

$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$。