• [1519] Software Company

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 一个软件开发公司要做两个程序项目。两个项目的结构是一样的,且这两个项目必须同时提交(即总时间等于最后完成的那个项目)。所以一个先完成对于整体时间的减少是没有帮助的。

    这个公司有n个雇员去做这项工作。为了更好的分配任务,每个项目都被分成独立的m个子项目。一个员工不能同时做多个子项目,但是两个员工可以同时做一个项目中不同的子项目。

    你的目标是尽快地完成项目。

  • 输入
  • 数据第一行包含两个整数n (1 <= n <= 100) 和 m (1 <= m <= 100)。其后的n行每行包含2个整数x, y (1 <= x, y <= 1000), 表示将花费对应雇员x个时间单位完成第一个程序项目中的任意子项目,y个时间单位完成第二个程序项目中的任意子项目。
  • 输出
  • 输出提交项目的最少时间。
  • 样例输入
  • 3 20
    1 1
    2 4
    1 6
    
  • 样例输出
  • 18
  • 提示
  • 来源
  • 本站或者转载
  • 操作

显示春菜