11228번 - Vending Machine 다국어

Sleazy Bob has happened upon a vending machine. After watching enough people buy tasty snacks, Bob has realized that the vending machine is broken!

Here’s what Sleazy Bob observes:

1. A person tries to buy a snack
2. The vending machine then checks to see if there are any left of that snack
3. If there are any left, the machine charges the person for that snack
4. If the machine successfully charges the person, it then gives the person a different snack! Possibly no snack at all, if the machine is out of the different snack!

Sleazy Bob notices that, although the machine is broken, it is at least consistent. Whenever a customer buys a snack from position i, the machine vends from position f(i), where f is some predictable function.

Now, Bob wants to make a profit from the machine. He wants to buy some snacks from the machine, and then turn around and sell the snacks he gets for the market price of the snack. This may be different from the vending price. If a cheap snack is at i, and an expensive snack is at f(i), he could rake in the cash! Assuming Bob can always find buyers for his snacks, what is the maximum net gain that Bob can obtain by buying some number, possibly zero, of snacks and turning around and selling them later? You may assume that Bob has enough money from other shady activities to cover the cost of buying any number of snacks from the vending machine.

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input begins with a line with a single integer n (1 ≤ n ≤ 100 000), which is the number of snack positions in the machine. Each of the next n lines contains 4 space-separated integers, f p m s, which describe a snack position in the machine, in order from 1 to n, where:

• f (1 ≤ f ≤ n) is the value of f(i). That is, it is the position from which the machine will vend when Bob buys from this position
• p (1 ≤ p ≤ 1 000 000) is the price Bob must pay to buy from this position
• m (1 ≤ m ≤ 1 000 000) is the market price of the snack at this position
• s (1 ≤ s ≤ 1 000 000) is the number of snacks at this position

Output a single line with a single integer, indicating the maximum profit Sleazy Bob can get from his nefarious abuse of the broken vending machine.