Problem : 318 - 晚餐時間

Problem Statistics

Solved Member: 25　　Submission: 99　　User Tried: 25

Statement:

HH是一個快餐店的老闆，現在依序來了n組客人，第i組客人有A_i個人一起來，HH很苦惱該如何準備煮菜，由於先煮後到的客人所點的菜會讓先到的客人不開心，所以HH會依序按照每一組的順序煮菜。但每一組中每個人所需要的煮菜時間與吃飯時間都不盡相同，所以HH要想辦法安排每組客人的煮菜順序，使得那組客人可以越早離開越好，這樣HH才有機會早點關店休息。

假設第一組客人進場時間為0，並且位置很多，可以容納下所有的人。

Input:Output:

第一行有一個數字n，表示一共有n組客人，然後是n組客人的資訊。

對於每組客人，第一個數字是A_i表示第i組客人一共有幾個人，接著有A_i行，每行兩個數字X_j, Y_j表示這組客人的第j個人要煮X_j單位時間，花費Y_j單位時間吃飯。

限制：
保證有50%的測試資料滿足:
1 ≤ n,A_i ≤ 500

保證所有的測試資料滿足:
1 ≤ n,A_i ≤ 250000
∑A_i ≤ 250000（客人總數在250000之內）
1 ≤ X_j, Y_j ≤ 10⁵

輸出n行，每行一個數字，第i行的數字表示第i組客人的離開時間。

Sample Input:Sample Output:

3
2
1 1
2 2
1
3 1
3
1 3
2 2
3 2

4
7
14

HINT:

範例測資依照廚師煮的順序排會變成：

第幾組	第幾個客人	開始煮的時間	開始吃(煮完)的時間	吃完的時間
1	2	0	2	4
1	1	2	3	4
2	1	3	6	7
3	1	6	7	10
3	3	7	10	12
3	2	10	12	14

注意到，雖然時間3-4之間第一組客人還在吃，但是由於時間3時廚師已經將第一組兩人的餐點都煮好了，就可以開始準備下一組人的餐點了。

Source:

102附中校內賽

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
2-1	1000ms	262144kb	10
2-2	1000ms	262144kb
3-1	1000ms	262144kb	10
3-2	1000ms	262144kb
4	1000ms	262144kb	10
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7-1	1000ms	262144kb	10
7-2	1000ms	262144kb
8-1	1000ms	262144kb	10
8-2	1000ms	262144kb
9-1	1000ms	262144kb	10
9-2	1000ms	262144kb
10-1	1000ms	262144kb	10
10-2	1000ms	262144kb