1973 Software Company

原文

時間制限:1000ミリ秒
メモリ制限:30000KB

問題

あるソフトウェア開発会社は、2つのプログラミング・プロジェクトを割り当てられた。両方のプロジェクトは同じ契約に含まれるため、両方は同時に手渡されなければならない。それらが早く終わったとしても、他を手伝うことはできない。

この会社には、仕事のためにn人の従業員がいる。2つのプロジェクトをより簡単に管理するため、それぞれはm個の独立なサブプロジェクトに分割された。1人の従業員は、同時に1つのサブプロジェクトで働くことしかできず、1つのサブプロジェクトのために働くことができるのは1人だけである。しかし、2人の従業員が同じプロジェクトの異なるサブプロジェクトのために、同時に働くことは可能である。

私達の目標は、プロジェクトをできるだけ早く終えることである。

入力

入力の最初の行は、テストケースの数を表す1つの整数t(1<=t<=11)を含み、各テストケースに対応する入力データが続く。
各テストケースの最初の行は、2つの整数n(1<=n<=100),m(1<=m<=100)を含み、n行の入力が続く。

各行は、ある従業員がそれぞれのプロジェクトについて、1つのサブプロジェクトを完了するために要する時間を秒単位で表した2つの整数を含む。
すなわち、ある行が2整数x,yを含んでいるなら、それは、その従業員は1つ目のプロジェクトのサブプロジェクトを完了するのにx秒、2つ目のプロジェクトのサブプロジェクトを完了するのにy秒を要するという意味である。

出力

各テストケースに対して、両方のプロジェクトを完了するのに要する最短の時間を秒単位で出力せよ。

入力の例

1
3 20
1 1
2 4
1 6

出力の例

18

出典

Tehran Sharif 2004 Preliminary

疑問

自分の仕事が終わった従業員は同じプロジェクト内の別の仕事を手伝えるか翻訳文からは曖昧な感じがします。