问题 D: 垦田计划

问题 D: 垦田计划

时间限制: 1 Sec  内存限制: 256 MB
提交: 40  解决: 30
[提交][状态][讨论版][命题人:]

题目描述

顿顿总共选中了 n 块区域准备开垦田地,由于各块区域大小不一,开垦所需时间也不尽相同。

据估算,其中第 i 块(1≤i≤n)区域的开垦耗时为 ti 天。

这 n块区域可以同时开垦,所以总耗时 tTotal 取决于耗时最长的区域,即:tTotal=max{t1,t2,…,tn}

为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间。

具体来说:

  • 在第 i块区域投入 ci 单位资源,便可将其开垦耗时缩短 1 天;
  • 耗时缩短天数以整数记,即第 i 块区域投入资源数量必须是 ci 的整数倍;
  • 在第 i块区域最多可投入 ci×(ti−k) 单位资源,将其开垦耗时缩短为 k天;
  • 这里的 k表示开垦一块区域的最少天数,满足 0<k≤min{t1,t2,…,tn};换言之,如果无限制地投入资源,所有区域都可以用 k天完成开垦。

现在顿顿手中共有 m单位资源可供使用,试计算开垦 n 块区域最少需要多少天?

输入

输入共 n+1行。

输入的第一行包含空格分隔的三个正整数 n,m,k,分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。

接下来 n 行,每行包含空格分隔的两个正整数 ti和 ci,分别表示第 i块区域开垦耗时和将耗时缩短 1天所需资源数量。

输出

输出一个整数,表示开垦 n 块区域的最少耗时。

样例输入

样例1
4 9 2
6 1
5 1
6 2
7 1
样例2
4 30 2
6 1
5 1
6 2
7 1

样例输出

样例1
5
样例2
2

提示

70%的测试数据满足:0<n,ti,ci≤1000 且 0<m≤10^6



全部的测试数据满足:0<n,ti,ci≤10^5且 0<m≤10^9

[提交][状态]