题目描述

小泽在一次远行中结识了擅长灵力操控的同伴小珅。两人联手收集了大量灵石，每一块灵石都蕴藏着不同的灵力。为了抵御突然出现的强大邪祟，他们决定使用灵石激活古老的召唤阵法。

一共有 $n$ 种不同的召唤阵法。第 $i$ 种阵法需要消耗 $c_i$ 点灵力，激活后可以造成 $d_i$ 点伤害。
小珅和小泽目前拥有的所有灵石，合计可以提供 $m$ 点灵力。每次激活阵法都会永久消耗对应灵力，且同一种阵法可以被无限次激活，只要灵力足够。

邪祟拥有 $H$ 点生命值。只要所有被激活阵法造成的总伤害 不小于 $H$，邪祟就会被击败。
在确保击败邪祟的前提下，小珅希望尽可能节省灵力，以备后用。请你计算：击败邪祟后，最多还能剩下多少点灵力？
如果无论如何都无法击败邪祟，请输出 $-1$。

输入格式

第一行，三个正整数 $n, m, H$。

接下来 $n$ 行，每行两个正整数 $c_i, d_i$。

输出格式

输出一个整数，表示击败邪祟后剩余的灵力最大值。
若无法击败邪祟，输出 $-1$。

输入输出样例

3 7 12
3 8
2 4
1 2

2

5 100 200
2 1
4 3
8 9
16 27
32 81

8

2 100000000 100
50000000 4
100000000 9

-1

说明/提示

样例解释

样例 1：
使用第 $1$ 种阵法 $1$ 次，第 $2$ 种阵法 $1$ 次。
总伤害 $= 8 + 4 = 12 \ge H$，消耗灵力 $= 3 + 2 = 5$。
剩余灵力 $= 7 - 5 = 2$。

样例 2：
使用第 $2,3,4$ 种阵法各 $1$ 次，第 $5$ 种阵法 $2$ 次。
总伤害 $= 3 + 9 + 27 + 81 \times 2 = 201 \ge H$，消耗灵力 $= 4 + 8 + 16 + 32 \times 2 = 92$。
剩余灵力 $= 100 - 92 = 8$。

样例 3：
即使耗尽所有灵石，最大可造成的总伤害仍小于 $H$，因此无法击败邪祟，输出 $-1$。

数据范围

• 前 $20\%$ 数据：$n \le 10,\ m \le 30$
• 前 $50\%$ 数据：$m \le 10^4$
• 对 $100\%$ 数据：
  $1 \le n \le 100$
  $1 \le m \le 10^9$
  $1 \le H \le 10^5$