信息学奥赛一本通(C++版)在线评测系统

本网站由成都石室中学、福建长乐一中信奥教练联合呈现。题库教师群:307432527,仅供教师加入
围观:初赛那点事!
提高 普及
你现在还未登录哦!
用户登录
注册新用户

1677:软件开发


时间限制: 1000 ms         内存限制: 131072 KB
提交数: 286     通过数: 131

【题目描述】

一个软件开发公司同时要开发两个软件,并且要同时交付给用户,现在公司为了尽快完成这一任务,将每个软件划分成$m$个模块,由公司里的技术人员分工完成,每个技术人员完成同一软件的不同模块的所用的天数是相同的,并且是已知的,但完成不同软件的一个模块的时间是不同的,每个技术人员在同一时刻只能做一个模块,一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序,求出公司最早能在什么时候交付软件。

【输入】

输入文件第一行包含两个由空格隔开的整数$n$和$m$。

接下来的$n$行每行包含两个用空格隔开的整数$d_1$和$d_2$,$d_1$表示该技术人员完成第一个软件中的一个模块所需的天数,$d_2$表示该技术人员完成第二个软件中的一个模块所需的天数。

【输出】

输出文件仅有一行包含一个整数$d$,表示公司最早能于$d$天后交付软件。

【输入样例】

3 20
1 1
2 4
1 6

【输出样例】

18

【提示】

【数据规模】

对于100%的数据,$1≤n≤100,1≤m≤100,1≤d_1,d_2≤100$。

【样例说明】

最快的方案是第一个技术人员完成第二个软件的$18$个模块,用时$18$天,第三个技术人员完成第一个软件的$18$个模块,用时$18$天,其余的模块由第二个技术人员完成,用时$12$天,做完所有的模块需要$18$天。如果第一个技术人员完成第二个软件的$17$个模块,第三个技术人员完成第一个软件的$17$个模块,其余的模块由第二个技术人员完成,需要用时$18$天,做完所有模块仍然需要$18$天,所以少于$18$天不可能做完所有模块。

提交 统计信息


本题库与《信息学奥赛一本通(C++版)》(科学技术文献出版社)配套,版权及相关事宜请与本书作者联系,本网站不作解答。
本网站属公益、非盈利性质,不涉及与书相关的商业活动,后期可能适当收取费用以支持网站的运行维护。
目前因个人编写水平有限,网站维护、网站安全方面及部分功能的开发尚不成熟,如遇疑问,请通过版主信箱联系。
感谢成都石室中学Wuvin、Qizy、Xehoth三位同学对本网站的支持,特别鸣谢北京师范大学ACM前校队易超、唐巧、洪涛同学。
版主信箱:ybt_mail@126.com