Fofão of Persia
By Lucas Mattioli e Simião Carvalho, UnB-Gama 
Brazil
By Lucas Mattioli e Simião Carvalho, UnB-Gama Brazil
It’s known that an organization of extraordinary beings is arising quickly. No one knows for sure from where or how it emerged, but it is remarkable how influential and loved are its members. Scrolls found decades ago indicate that there would be a time when an organization would bring happiness to mankind. And, as it seems, this time has come; Hurricane Cart is here. The scriptures also give name to the legendary beings who are part of the organization: Popeye, Captain America, Patatá, Ben 10, Spider Man, Mickey Mouse, Woody Woodpecker and their supreme leader: Fofão. Because of his from-another-world skills, he is also known as Fofão of Persia.
Despite his superiority, Fofão of Persia has a problem. His city is formed by neighborhoods and bidirectional streets to connect them. There is a wall in each street. Fofão is aboard the Hurricane Cart’s vehicle at neighborhood P, but all the other members are at neighborhood D. In order to gather all members together and break Exodia free, Fofão wants to get to neighborhood D (it’s possible to get to any neighborhood leaving from any neighborhood). When the vehicle enters a street, Fofão doesn’t resist the temptation: he jumps off the vehicle and applies a backflip in that street’s wall and then gets back to the vehicle. Each applied backflip provides happiness to the fans inside the vehicle by an amount of Fi, which depends on the wall’s height. The sole of Fofão’s shoes starts with an amount B of carbon rubber and, for each backflip in a wall, the current amount of carbon rubber decreases by Si, which depends on the wall conditions. If at any time the amount of carbon rubber of Fofão’s sole is X and he tries to apply a backflip in a wall that has Si > X, Fofão explodes. Fofão (and the vehicle’s driver) doesn’t mind passing through the same street several times; the only thing he wants is to get to neighborhood D alive and having provided the maximum possible happiness to his fans. Note that if at any time the vehicle arrives at neighborhood D, the driver will take a nap and no street will be traveled from there on. Write a program to help Fofão: what is the maximum happiness he can bring to his fans while traveling from neighborhood P to neighborhood D?
The input describes a single test. The first line consists of two integers N and M, representing the number of neighborhoods and the number of streets, respectively. The neighborhoods are numbered from 1 to N. (2 <= N <= 100, 1 <= M <= (N * (N - 1)) / 2)
The second line consists of two integers P and D, representing the source neighborhood and the destination neighborhood, respectively. (1 <= P, D <= N and P != D)
The third line consists of a single integer B, which represents the initial amount of carbon rubber on the sole of Fofão’s shoes. (1 <= B <= 1000).
The M following lines describe the streets (and its corresponding wall). Each street is described by four integers: Xi, Yi, Fi, Si, representing, respectively, the first neighborhood connected to the street, the second neighborhood connected to the street, the amount of happiness that is provided to the fans when Fofão applies a backflip in that street’s wall and the amount of carbon rubber that is decreased from the sole of Fofão’s shoes when a backflip is applied in that street’s wall. (1 <= Xi, Yi <= N, 1 <= Si <= 1000, 1 <= Fi <= 10^9 and Xi != Yi)
Print a line with an integer T that represents the maximum amount of happiness Fofão can provide to his fans while traveling from neighborhood P to neighborhood D. If it’s impossible to Fofão to get to neighborhood D alive, print -1.
| Input Samples | Output Samples |
|
4 5 |
36 |
|
2 1 |
-1 |