TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

面試麵屋牡丹未果的赤井心,憤而在麵屋牡丹本店對面開了一家烏龍麵,想奪取麵屋牡丹的客源。為了具備和麵屋牡丹對抗的實力,赤井心開始認真研究烏龍麵的配方。她得知了一碗烏龍麵由以下兩個要素組成:麵團配方和調味料配方。
於是赤井心備齊了 N 種麵團和 N 種調味料,準備大展身手,搭配出 N 碗烏龍麵。她發現每種麵團都與特定一種調味料會產生「絕配」。當第 i 種麵團和某種調味料是絕配,會產生 ci 的美味程度;但也可能搭配特定一種調味料後會製造出地獄組合,損失 di 點的美味程度。
如果某組麵團和調味料的搭配不是絕配,也不是地獄組合則美味程度為 0。浪費食材是不可饒恕的事,因此一種麵團一定跟洽一種調味料搭配,一種調味料也跟洽一種麵團搭配。
沒有學過演算法的赤井心來找你幫忙,她聽說你是個演算法高手。你能想辦法讓總美味程度最大嗎?

Input Format

1 行輸入 N,代表有 N 種麵團與 N 種調味料。
2 到第 N+1 行,每行有兩個數字 ai,ci,表示第 i 種麵團和第 ai 種調味料會產生絕配,並且獲得 ci 美味程度。
N+2 到第 2N+1 行,每行有兩個數字 bi,di,表示第 i 種麵團和第 bi 種調味料會產生地獄組合,並且損失 di 美味程度,若 bi=di=0,則代表第 i 種麵團不會跟任何調味料產生地獄組合。

  • 1N5×105
  • 1aiN
  • 0biN
  • 0ci,di109
  • aibi

Output Format

一個整數 k,代表最大的總美味程度。

Sample Input 1

3
2 1
1 3
1 2
0 0
0 0
0 0

Sample Output 1

4

Sample Input 2

3
2 1
1 3
1 2
3 1
3 4
3 5

Sample Output 2

2

Hints

Problem Source

第九屆高一生程式設計排名賽 pF

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1 2
1 5000 524288 65536 1 2
2 5000 524288 65536 2
3 5000 524288 65536 2
4 5000 524288 65536 2
5 5000 524288 65536 2
6 5000 524288 65536 2
7 5000 524288 65536 2
8 5000 524288 65536 2
9 5000 524288 65536 2
10 5000 524288 65536 2
11 5000 524288 65536 2
12 5000 524288 65536 2
13 5000 524288 65536 2
14 5000 524288 65536 2
15 5000 524288 65536 2
16 5000 524288 65536 2
17 5000 524288 65536 2
18 5000 524288 65536 2
19 5000 524288 65536 2
20 5000 524288 65536 2
21 5000 524288 65536 2
22 5000 524288 65536 2
23 5000 524288 65536 2
24 5000 524288 65536 2
25 5000 524288 65536 2
26 5000 524288 65536 2