【VIP专享】2014年安庆市青少年信息学奥林匹克竞赛中学组试题

2014年安庆市青少年信息学奥林匹克竞赛第四题工程安排（project）问题描述

爸爸的公司中标两个道路修建的工程，建设方要求两个工程完成后一并交付。为了尽快交付，爸爸的公司雇佣了N支施工队，并将两个工程都划分成M个相同的小段，某支施工队完成同一个工程的小段，所用的工期是相同的。下图所示即将工程（一）和工程（二）都分成3个小段。

为了保证工程质量和责任包干，一个小段只能有某一施工队独立完成，当某一施工队完成某一小段工程之后，可以接着对任何一个没有开工的工程小段施工，无论是工程（一）还是工程（二）。

工程（一）

标段1标段2标段3工程（二）

标段I标段2标段3请你帮助爸爸计算工程交付的最短工期。

输入描述

第一行，两个整数N和M，意义如题所述。

接下来N行，每行两个整数X和Y，X表示该支施工队完成工程（一）小段所需的天数；Y表示该支施工队完成工程（二）小段所需的天数。

输出描述

一个整数，表示工程交付的最短工期。

输入样例

3201124

2014/3/30安庆第6页共7页2014年安庆市青少年信息学奥林匹克竞赛16输出样例

18数据范围

1<=N<=1001<=M<=1001<=X<=1001<=Y<=100

2014/3/30安庆第7页共7页