TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

59.0% (23/39)

Tags

Description

回憶一下你的老埃及打印機。

你有一個打印機、一堆金屬字母塊。打印機支援以下的操作,且每個操作都要一塊金幣:

        .在打印機的尾端添入一個金屬字母塊
        .複印出打印機中的字母塊所排出的字
        .從打印機的尾端拿走一個金屬字母塊

然後你曾經有一個任務,就是用最小的花費把一堆字母全部打印出來(以任意的順序)。
當然,一開始打印機中沒有任何金屬字母塊,打印完成後也不需要把金屬字母塊清空。
成功的解決任務後,你獲得了一個100 塊。

現在,科技進步了,你的財產也從一個老打印機進化成很多臺雷射印表機。
根據公司的影印細則,每台雷射印表機一開始都被指定了一些印表工作,而且優先權越高的列印工作應該越先被完成。
不幸的是,在列印某些工作時,印表機的墨水會用盡。
這時,當下正在列印的工作以及此台印表機所有尚未完成的工作會全部被加到某台可以列印的印表機的等待佇列當中。

當然,這台印表機也無法再印任何的東西。

不過注意,如果發現加入印表機佇列的新工作比正在列印的工作優先權還高,那你應該要停止正在列印的工作,
並且立刻去列印優先權較高的新工作。

那你最後會在什麼時候完成所有的列印工作呢?

1. Pij越大代表該工作優先權越高
2. 若一個工作被打斷了(或墨水用完了),那下次必須從頭印。
3. 當然,每個印表機是可以同時列印的。

Input Format

第1行:
有一個正整數N,代表共有N臺雷射印表機。

第2行到第N+1行:
第i+1行的一開始會有一個非負整數Mi,代表第i臺雷射印表機一開始被指定了Mi件工作。
接下來會有Mi個整數對,第j個數對(Pij, Tij)代表第i臺雷射印表機的第j件工作的優先權是Pij、需要費時 Tij的時間。
保證任兩列印工作的優先權都相異。

第N+2行:
一個正整數E,代表總共有E個事件。

第N+3行到第N+E+2行:
第N+k+2行依序有三個正整數Tk Rk Ak,代表在時間點Tk的時候,編號Rk的雷射印表機墨水用完了,
且把剩餘(包括正在印)的工作全部加到編號Ak的印表機。

保證T1≦T2≦T3≦…≦Tn且Ak一定還有剩餘的墨水。

Output Format

第一行:一個正整數F,代表所有工作印完的時間。

Sample Input 1

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

Sample Output 1

15

Hints

佔總分50%的測試資料中,
1≦N≦5,000,總列印工作數不超過5,000件。

對於所有的測試資料而言,1≦N≦100,000,總列印工作數不超過1,000,000件。
答案不會超過231-1,且0≦E<N。

Problem Source

原TIOJ1671 / 建國中學99年校內培訓contest #2 prob 2
problem setter:suhorng

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10