TopCoder

欸我好笨ㄛ
Why am I so weak mie pu

User's AC Ratio

47.8% (11/23)

Submission's AC Ratio

18.3% (22/120)

Tags

Description

植物園高級中學的圖書館進新書了!

《費曼怪話集》是一本充滿怪話的新書,裡面記載了資訊競賽選手受到費曼侵蝕精神(?)後所講出來的怪話,如:

「你要不要去當物理治療師?」
「蛤」
「這樣大家就會付錢來被你電」

由於同一系列書籍的上一部 ——《ZCK 語錄》—— 受到廣泛的好評甚至還出了週邊撲克牌,因此許多人搶著要閱覽這本新書。
想要閱讀這本書只有一個方法:進入圖書館的新書區,坐下來一口氣讀完這本書才能離開(否則你也會開始講怪話)。

不幸的是,《費曼怪話集》實在有太多怪話了,一個圖書館只能有一本,不然整間都會被費曼侵蝕。

植物園高級中學的學生分成兩種: LW(意義不明)。
同一種學生可以共享閱讀時間(不同人可以在同一時間閱讀不同頁),
但是不同類的學生不能一起閱讀(否則會被強制湊為 CP )。

現在,給你每個學生抵達圖書館的時間點以及他們完整閱讀完《費曼怪話集》所需的時間,
請求出所有人最早要在哪個時間點才能都閱讀完《費曼怪話集》?

Input Format

第一行有一個正整數 T,代表有幾筆測資。

每一筆測資,第一行輸入兩個整數 L,W,分別代表 LW 類型學生的數量。

接下來的 L 行每行有 2 個整數 ai,pi
代表第 iL 型學生會在時間點 ai 到達圖書館,
並且需要閱讀 pi 單位時間才能讀完《費曼怪語錄》。

接下來的 W 行每行有 2 個整數 bj,qj
代表第 jW 型學生會在時間點 bj 到達圖書館,
並且需要閱讀 qj 單位時間才能讀完《費曼怪語錄》。

對於所有測資,保證 L,W3000,1ai,bj107,1pi,qj105
保證 max(L,W)10000

Output Format

輸出一個正整數,代表所有人最早要在哪個時間點才能都閱讀完《費曼怪話集》。

Sample Input 1

2

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

8
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,W10 13
3 7~12 pi=qj=1 17
4 5~6, 13~16 qj=1 29
5 0~20 無額外限制 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2 5
1 1000 131072 65536 2 5
2 1000 131072 65536 2 5
3 1000 131072 65536 2 5
4 1000 131072 65536 2 5
5 1000 131072 65536 2 4 5
6 1000 131072 65536 2 4 5
7 1000 131072 65536 2 3 5
8 1000 131072 65536 2 3 5
9 1000 131072 65536 3 5
10 1000 131072 65536 3 5
11 1000 131072 65536 3 5
12 1000 131072 65536 3 5
13 1000 131072 65536 4 5
14 1000 131072 65536 4 5
15 1000 131072 65536 4 5
16 1000 131072 65536 4 5
17 1000 131072 65536 5
18 1000 131072 65536 5
19 1000 131072 65536 5
20 1000 131072 65536 5