g5-09064. 预算内的领先 未做

卡牌游戏里有 $n$ 种流派、$m$ 张收藏卡，第 $i$ 张卡当前属于流派 $p_i$，花 $c_i$ 金币可以把它改成任意流派。

小林有预算 $X$ 金币，要使最后 $1$ 号流派的卡严格多于其他每一种流派。预算内 $1$ 号流派最终最多能有多少张？无论如何做不到输出 $-1$。

第一行三个整数 $n,m,X$。接下来 $m$ 行，每行两个整数 $p_i,c_i$。

一行一个整数：预算内可行的最大终态张数；不可行输出 $-1$。

样例 1：各终态最少花费 $f(1)=7,f(2)=2,f(3)=2,f(4)=4,f(5)=7$；预算 $2$ 内可行的是 $k=2,3$，最多 $3$ 张。样例 2：预算 $1$ 内任何终态都不可行，输出 $-1$。

$1\le n,m\le 1000$，$1\le X\le 10^{15}$，$1\le p_i\le n$，$1\le c_i\le 10^9$。