No testdata at current.

题目描述

有 $n$ 个物品，第 $i$ 个物品有两个属性 $k_i,b_i$ ，表示它在时刻 $x$ 的价值为 $k_i\times x+b_i$ 。

当前处于时刻 $0$，你可以选择不超过 $m$个物品，使得存在非负整数时刻 $t$，你选择的所有物品的总价值大于等于 $S$。

给出 $S$，求 $t$的最小值。

输入格式

第一行三个整数 $n,m,S$ 。

接下来 $n$行，第 $i$行两个整数 $k_i,b_i$。

输出格式

一行一个整数表示答案。

样例

样例 1 输入

3 2 100
3 9
-2 50
4 1

样例 1 输出

13

样例 1 解释：选择 号物品。

样例 2 输入

3 2 100
-1 49
-2 50
1 -998244353

样例 2 输出

998244453

样例 $2$ 解释：选择$3$号物品。

数据范围与提示

对于 $100\%$的数据，有 $1\le m\le n \le10^6$，$-10^9\le b_i \le 10^9$，$-10^6 \le k_i \le 10^6$，$0\le S\le10^{18}$，数据保证有解，且答案不超过 $10^{9}$。