TopCoder

Thumb 148522015 226355662574319 5804619006965446972 n
欸我好笨ㄛ
Why am I so weak mie pu

User's AC Ratio

52.9% (9/17)

Submission's AC Ratio

19.8% (20/101)

Description

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

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

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

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

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

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

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

Input Format

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

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

接下來的 $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

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

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, 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

Testdata and Limits

No. Time Limit (ms) Memory Limit (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