UOJ Logo LFYZ Online Judge

LFYZOJ

#348. 【2018 国庆雅礼 NOIP 培训】D6T1 Merchant

统计

问题描述

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

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

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

输入格式

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

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

输出格式

一行一个整数表示答案。

样例一

Input

3 2 100
3 9
-2 50
4 1

Output

13

Explanation

选择 1, 3号物品。

样例二

Input

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

Output

998244453

Explanation

选择3号物品。

子任务

对于所有数据,有 $1 \le m \le n \le 10^6 ,−10^9 \le b_i \le 10^9 ,−10^6 \le k_i \le 10^6 ,0 \le S \le 10^18$。

数据保证有解,且答案不超过 $10^9$ 。

  • Subtask1(22%), $n \le 20$.
  • Subtask2(36%), $n \le 10^5 ,0 \le k_i \le 10^4$ .
  • Subtask3(8%), $k_i \le 0$.
  • Subtask4(12%), $n \le 10 5$ .
  • Subtask5(22%), 没有特殊的约束。

时间限制: $1\mathrm{s}$

内存限制: $512\mathrm{MB}$

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。