问题 26029 --软件公司

26029: 软件公司

时间限制: 1 Sec  内存限制: 128 MB
提交: 29  解决: 19
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

一家软件开发公司有两个项目,并且这两个项目都由相同数量的m个子项目组成,对于同一个项目,每个子项目都是相互独立且工作量相当的。由于时效性,两个项目必须同时被完成,如果其中一个完成的早了,那么这两个项目都会无效。

这家公司有n名程序员分配给这两个项目,每个子项目必须由一名程序员一次完成,多名程序员可以同时做同一个项目中的不同子项目

求公司完成两个项目的最少时间。

输入

第一行两个正整数nm1<=n<=100,1<=m<=100)

接下来n行,每行包含两个整数,xy。分别表示每个程序员完成第一个项目的子程序的时间,和完成第二个项目子程序的时间。每个子程序耗时也不超过100

输出

包含一个整数,表示两个项目同时完成的时间

样例输入

3 20
1 1
2 4
1 6

样例输出

18

提示


【样例解释】



    第一个人做182项目,耗时18;第二个人做21项目,22项目耗时12;第三个人做181项目,耗时18



 



【数据范围】



对于30%的数据,n<=30.



对于60%的数据,n<=60.

来源

[提交][状态]