Limits 2s, 512 MB

X Game Studio is working on their next super-hit game. The game is quite simple. The player has a car and there are nn bridges in front of them. The player has to use their car to cross each bridge once, they can, however, choose in what order to cross the bridges. The iith bridge has a fuel usage value fif_i and a fuel refill value rir_i. When the player’s car crosses the bridge, the car loses fif_i units of fuel, but at the end of the bridge, the car gets additional rir_i amounts of fuel. Of course, if the fuel ever becomes negative, the car will stop and the player will lose. The player has one chance to initially fill the car’s fuel by some amount. So the player needs to do some calculations to know how much fuel to keep in the beginning and in what order to cross the bridges. If they keep too little fuel, the car will stop on some bridge; if they keep too much, they waste their in-game currency.

The developers found that this was too easy, so they added some more mechanics. The bridges can have some locks at their entrance. In particular, the iith bridge has a lock with the color lil_i in its entrance. If lil_iis 0, then the bridge has no lock. Also, the iith bridge has a key with the color kik_i at the end of the bridge. Here, kik_i being 0 means the bridge has no key. Note that multiple locks might have the same color, but for each color, there is at most one key. This lock-key mechanic creates more restrictions in the game, as to open a lock, player must have the corresponding key (keys can be used multiple times). Now happy with the rules, the developers have made the levels so that it’s possible to finish the level. But now they need to know the minimum amount of fuel the player needs to fill initially to cross all the bridges as this value can be used to quickly give verdicts instead of making players fumble around with bridges. This is where you come in, The level description is given. You have to find the minimum initial fuel needed to make sure the player can finish the game.


The first line of input will have a positive integer TT, the number of independent test cases. Each test case will begin with a positive number nn, the number of bridges. Then the next nn lines each will have 4 space-separated values denoting fi,ri,li,kif_i, r_i, l_i, k_i.

  • 1T1051 \leq T \leq 10^5

  • 1n1051 \leq n \leq 10^5

  • 1fi,ri1051 \leq f_i, r_i \leq 10^5%

  • 0li,ki1050 \leq l_i, k_i \leq 10^5

  • On a level, no two bridges have the same positive kik_i.

  • It is guaranteed that there is some sequence of bridges using which the player can finish the level.

  • The sum of nn over all test cases 5×105\leq 5 \times 10^5


For each testcase, output the minimum initial amount of fuel the player needs to fill initially to finish the game in a separate line.


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


Login to submit.


20% Solution Ratio
rebornEarliest, 1w ago
rebornFastest, 1.7s
rebornLightest, 28 MB
rebornShortest, 5445B
Toph uses cookies. By continuing you agree to our Cookie Policy.