|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||51||16||9||21.951%|
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:
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:
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.
3 1 2 3 1 2 3 4 1 3 4 5 1
3 2 2 3 8 3 1 5 6 1 9 4 7
5 5 9 2 2 1 1 7 4 2 3 6 3 2 2 9 6 1 4 5 1