植物園高級中學的圖書館進新書了!
《費曼怪話集》是一本充滿怪話的新書,裡面記載了資訊競賽選手受到費曼侵蝕精神(?)後所講出來的怪話,如:
「你要不要去當物理治療師?」
「蛤」
「這樣大家就會付錢來被你電」
由於同一系列書籍的上一部 ——《ZCK 語錄》—— 受到廣泛的好評甚至還出了週邊撲克牌,因此許多人搶著要閱覽這本新書。
想要閱讀這本書只有一個方法:進入圖書館的新書區,坐下來一口氣讀完這本書才能離開(否則你也會開始講怪話)。
不幸的是,《費曼怪話集》實在有太多怪話了,一個圖書館只能有一本,不然整間都會被費曼侵蝕。
植物園高級中學的學生分成兩種: L
和 W
(意義不明)。
同一種學生可以共享閱讀時間(不同人可以在同一時間閱讀不同頁),
但是不同類的學生不能一起閱讀(否則會被強制湊為 CP )。
現在,給你每個學生抵達圖書館的時間點以及他們完整閱讀完《費曼怪話集》所需的時間,
請求出所有人最早要在哪個時間點才能都閱讀完《費曼怪話集》?
第一行有一個正整數 $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$
輸出一個正整數,代表所有人最早要在哪個時間點才能都閱讀完《費曼怪話集》。
第一筆範例測資:
你可以先讓 L
學生看完(時間點 4),
再讓 W
學生一起看完(時間點 8)。
第二筆範例測資:
你可以先讓第 1, 3, 4 位 W
學生一起看完(時間點 13),
再讓三位 L
學生一起看完(時間點 22),
最後讓第 2 位 W
學生看(時間點 23)。
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 |