2216 . 費曼怪話集
TopCoder
Tags
Description
植物園高級中學的圖書館進新書了！
《費曼怪話集》是一本充滿怪話的新書，裡面記載了資訊競賽選手受到費曼侵蝕精神（？）後所講出來的怪話，如：
「你要不要去當物理治療師？」
「蛤」
「這樣大家就會付錢來被你電」
由於同一系列書籍的上一部 ——《ZCK 語錄》—— 受到廣泛的好評甚至還出了週邊撲克牌，因此許多人搶著要閱覽這本新書。
想要閱讀這本書只有一個方法：進入圖書館的新書區，坐下來一口氣讀完這本書才能離開（否則你也會開始講怪話）。
不幸的是，《費曼怪話集》實在有太多怪話了，一個圖書館只能有一本，不然整間都會被費曼侵蝕。
植物園高級中學的學生分成兩種： L 和 W（意義不明）。
同一種學生可以共享閱讀時間（不同人可以在同一時間閱讀不同頁），
但是不同類的學生不能一起閱讀（否則會被強制湊為 CP ）。
現在，給你每個學生抵達圖書館的時間點以及他們完整閱讀完《費曼怪話集》所需的時間，
請求出所有人最早要在哪個時間點才能都閱讀完《費曼怪話集》？
Input Format
第一行有一個正整數 $T$，代表有幾筆測資。
每一筆測資，第一行輸入兩個整數 $L, W$，分別代表 L 和 W 類型學生的數量。
接下來的 $L$ 行每行有 $2$ 個整數 $a_i, p_i$ ，
代表第 $i$ 個 L 型學生會在時間點 $a_i$ 到達圖書館，
並且需要閱讀 $p_i$ 單位時間才能讀完《費曼怪語錄》。
接下來的 $W$ 行每行有 $2$ 個整數 $b_j, q_j$ ，
代表第 $j$ 個 W 型學生會在時間點 $b_j$ 到達圖書館，
並且需要閱讀 $q_j$ 單位時間才能讀完《費曼怪語錄》。
對於所有測資，保證 $L, W \le 3000, 1 \le a_i, b_j \le 10^ 7, 1 \le p_i, q_j \le 10^ 5$ 。
保證 $\sum max(L, W) \le 10000$
Output Format
輸出一個正整數，代表所有人最早要在哪個時間點才能都閱讀完《費曼怪話集》。
Sample Input 1
1 2
1 3
2 4
3 3
3 4
7 4
8 9
12 5
8 2
14 1
6 7
3 9
Sample Output 1
23
Hints
第一筆範例測資：
你可以先讓 L 學生看完（時間點 4），
再讓 W 學生一起看完（時間點 8）。
第二筆範例測資：
你可以先讓第 1, 3, 4 位 W 學生一起看完（時間點 13），
再讓三位 L 學生一起看完（時間點 22），
最後讓第 2 位 W 學生看（時間點 23）。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~8 | $L, W \le 10$ | 13 |
| 3 | 7~12 | $p_i = q_j = 1$ | 17 |
| 4 | 5~6, 13~16 | $q_j = 1$ | 29 |
| 5 | 0~20 | 無額外限制 | 41 |