2016-17 Woburn Challenge Finals Round - Senior Division

Angus and Bessie are the most well-known grenadiers in Bo Vine's army, and they're constantly trying to out-do one another. Even on the very eve of the war's first major battle, they've ended up in an argument! On this occasion, they're fighting over how to split up the army's supply of grenades – of course, each of them wants the most powerful grenades to themselves! In an attempt at fairness, they're going to play a game to divide up the grenades.

There are ~N~ ~(1 \le N \le 300\,000)~ boxes of grenades. The ~i~-th box contains ~G_i~ ~(1 \le G_i \le 300\,000)~ grenades, with the ~j~-th of those grenades having a "grenade power" of ~P_{i, j}~ ~(1 \le P_{i, j} \le 10\,000\,000)~, indicating its explosive strength. There are at most ~300\,000~ grenades in total across all of the boxes.

Angus and Bessie will take turns performing actions, with Angus going first, until each of the grenades has been taken by one of them. All ~N~ of the boxes are initially sealed. In one turn, a cow may either unseal a sealed box, or take one grenade from an unsealed box. Both cows will make optimal actions with the goal of maximizing the total grenade power of the grenades that they'll get their hands on throughout the game (and thus minimizing the total grenade power obtained by their opponent).

To make things more exciting, the entire game will actually be independently re-played ~M~ ~(1 \le M \le 300\,000)~ separate times. Before the ~i~-th time the game gets played, a single grenade will get swapped out for a slightly different one. In particular, the ~B_i~-th grenade in the ~A_i~-th box ~(1 \le A_i \le N, 1 \le B_i \le G_{A_i})~ will be replaced with a new grenade whose grenade power is ~D_i~ ~(-1 \le D_i \le 1)~ larger than that of the removed grenade. It's guaranteed that the new grenade's power will still be positive. Each such replacement will carry over to all subsequent times the game gets played, and the new grenade itself may get replaced later on.

Help Angus and Bessie determine the outcome of their set of games by predicting how much grenade power each of them will end up with each time they play. Rather than outputting all ~2M~ such values (the grenade power obtained by Angus and Bessie each time they play), you only need to compute the sum of Angus's ~M~ values, as well as the sum of Bessie's ~M~ values.

In test cases worth ~5/32~ of the points, ~N = 1~, ~M \le 2\,000~, and ~G_1 \le 2\,000~.
In test cases worth another ~4/32~ of the points, ~N = 1~.
In test cases worth another ~6/32~ of the points, ~N \le 2\,000, M \le 2\,000~, and there are at most ~2\,000~ grenades in total.

Input Specification

The first line of input consists of two space-separated integers ~N~ and ~M~.
~N~ lines follow, the ~i~-th of which consists of an integer ~G_i~, followed by a space, followed by ~G_i~ space-separated integers ~P_{i, 1}, \dots, P_{i, G_i}~ (for ~i = 1 \dots N~).
~M~ lines follow, the ~i~-th of which consists of three space-separated integers ~A_i~, ~B_i~, and ~D_i~ (for ~i = 1 \dots M~).

Output Specification

Output a single line consisting of two space-separated integers – the total grenade power obtained by Angus and Bessie, respectively.

Sample Input

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

Sample Output

17 29

Sample Explanation

After the first grenade replacement, assuming both cows play optimally, Angus will end up obtaining ~5~ grenade power (for example, he may get ~4~ from the ~1~st grenade in the ~1~st box, and ~1~ from the ~1~st grenade in the ~3~rd box), while Bessie will obtain ~10~ from the remaining grenades.
After the second replacement, Angus will obtain ~6~ while Bessie will obtain ~10~. After the third replacement, Angus will obtain ~6~ while Bessie will obtain ~9~. In total, then, Angus will have obtained ~5 + 6 + 6 = 17~ grenade power, while Bessie will have obtained ~10 + 10 + 9 = 29~.