KAIST 社团联合会是一个根据社团活动记录来分配大学社团经费的学生机构。Taein 是 KAIST 的马拉松社团 RUN 的成员，他加入了 KAIST 社团联合会，希望能让 RUN 获得更多经费。

KAIST 共有 $N + 1$ 个社团，编号为 $1$ 到 $N + 1$。RUN 的编号为 $N + 1$。KAIST 社团联合会给每个社团分配一个非负整数作为评分。一个社团的排名定义为：（评分比该社团高的社团数量）+ 1。请注意，可能会有多个社团并列相同排名。社团的排名越靠前（即排名数值越小），获得的经费机会就越好。

Taein 希望篡改评分以偏袒 RUN。目前，除 RUN 以外的每个社团的评分都已经确定——对于每个 $1 \le i \le N$，社团 $i$ 的评分为 $a_i$。Taein 可以在满足以下条件的情况下修改每个社团的评分：

• 在 Taein 修改后，每个社团的评分不能增加。
• 在 Taein 修改后，每个社团的评分必须是一个非负整数。
• 如果 Taein 将社团 $i$ 的评分降低了 $T$，则 KAIST 社团联合会的怀疑度将增加 $T \times b_i$，其中 $b_i$ 是根据每个社团的影响力和信息收集能力为该社团确定的一个整数。
• 总怀疑度必须小于 $K$。如果怀疑度达到或超过 $K$，将会触发内部调查，这可能会给 Taein 带来麻烦。

在篡改评分后，Taein 将填入 RUN 的评分，从而完成经费分配流程。为了避免引起怀疑，Taein 希望在保持 RUN 的排名足够靠前（以获得所需的所有资金）的同时，让 RUN 的评分尽可能低。你需要求出 RUN 的最小可能初始评分，使得 RUN 的最终排名至多为 $X$，且存在一种篡改方案使得增加的怀疑度小于 $K$。由于 RUN 也是一个社团，因此该评分也必须是一个非负整数。

输入格式

第一行包含三个空格隔开的整数 $N, K, X$。

接下来的 $N$ 行中，第 $i$ 行包含两个空格隔开的整数 $a_i$ 和 $b_i$。

输出格式

输出 RUN 的最小可能初始评分，使得 RUN 的最终排名至多为 $X$，且存在一种篡改方案使得增加的怀疑度小于 $K$。由于 RUN 也是一个社团，因此该评分也必须是一个非负整数。

数据范围

• $1 \le N \le 10^5$
• $1 \le K \le 10^{18}$
• $1 \le X \le N + 1$
• $0 \le a_i \le 10^6$
• $1 \le b_i \le 10^6$

样例

输入样例 1

4 10 2
100 1
2 100000
50 1
30 8

输出样例 1

41

输入样例 2

5 15 3
15 4
24 1
10 3
24 2
2 8

输出样例 2

10