408372: GYM103107 L Labi-Ribi

Labi-ribi is a newly published STG. As everyone knows, wor is a TouHouProject-Player. As a TouHouProject-Player, he must want to play such funny STG.

Labi-ribi has $$$n$$$ stages. Each stage has a boss at level $$$h_i$$$. Only when player's level is greater than or equal to boss's level, the player can beat boss and clear this stage. After beating $$$i$$$-th boss, the level of all remaining bosses will be increased $$$a_i$$$ points, and the player's level will be increased $$$b_i$$$ points.

wor want to challenge the hardest. Therefore, he wants to use the minimun initial level to clear all stages. Can you tell him the minimun initial level that he need to clear all stages?

Labi-ribi is a great game, so there is an additional DLC annually. Now there has been $$$q$$$ DLCs. For one DLC, it provides a brand new stage. wor is so patient that every time an additional DLC was provided, he would play Labi-ribi again. Similarly, for each additional DLC, wor wants to know the minimun initial level that can clear all stages. Can you help him?

The first line contains one integer $$$n ~ (1 \le n \le 10^5)$$$ denoting the number of initial stages.

The second line contains $$$n$$$ integers $$$h_1, h_2, \cdots, h_n ~ (-10^9 \le h_i \le 10^9)$$$ denoting the initial level of $$$i$$$-th boss

Then $$$n$$$ lines follows, the $$$i$$$-th of which contains two integers $$$a_i, b_i ~ (-10^9 \le a_i, b_i \le 10^9)$$$.

The $$$n+3$$$-th line contains one integer $$$q ~ (0 \le q \le 1000)$$$ denoting the number of additional DLCs.

Then $$$q$$$ lines follows, the $$$i$$$-th of which contains three integers $$$h_i, a_i, b_i$$$ denoting the arguments for the $$$i$$$-th DLC.

Output $$$q+1$$$ lines in total.

The first line contains one integer denoting the minimum initial level that he needs to clear all stages.

Then $$$q$$$ lines follows, the $$$i$$$-th of which contains one integer for the minimum initial level that he needs to clear all stages after acquiring the $$$i$$$-th additional DLC.

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

2
3

1
100
2 1
2
200 102 1
1 1 100

100
201
102