N. Infinite Money Glitch II
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rami got tired of working for a low salary. He asked for a raise, but Yessine told him that the best he can do is buy him a new Shisha. Rami got angry and quit the company. Now he wants to get rich quickly. So, he decided to use the knowledge he acquired at Iceberg Corporation and become a cryptocurrency trader.

In fact, the cryptocurrency market has $$$n$$$ currencies. Also, there are $$$m$$$ pairs of currencies that can be exchanged. For each pair $$$(u,v)$$$, there is a rate $$$r_{u,v}$$$ that represents the exchange rate of the currency $$$u$$$ to the currency $$$v$$$. But that exchange is not free, there is a fee $$$f_{u,v}$$$ that is deducted from the exchanged amount according to the following formula: $$$$$$ \mathrm{amount}(v) = r_{u,v}\times (\mathrm{amount}(u)-f_{u,v}) $$$$$$

Rami is broke, but he can still borrow up to $$$x$$$ amount of money of currency $$$0$$$ from Oussama. He wants to know the minimal integer amount of money he should spend so that he can end up with strictly more money by only converting currencies and make a win.

Rami can exchange currencies as many times as he wants. But, the final amount must be in the currency $$$0$$$.

Formally, let $$$z_1$$$ be the amount that Rami has borrowed from Oussama expressed in currency $$$0$$$, and let $$$z_2$$$ be the amount that he got after the series of conversions, and expressed in currency $$$0$$$ as well. Rami will make a win if and only if $$$\Delta z= z_2-z_1 \gt 0$$$

Input

The first line contains three integers $$$n,m,x,$$$ with $$$1\le n\le 500,$$$ $$$1\le m \le 4000$$$ and $$$0\le x \le 10^9$$$

The next $$$m$$$ lines contain each $$$4$$$ numbers $$$u_i,v_i,r_{u_i,v_i},f_{u_i,v_i}$$$ with:

  • $$$u_i\rightarrow v_i:$$$ denotes an exchange from currency $$$u_i$$$ to currency $$$v_i$$$, where $$$1\le u_i \ne v_i \le n$$$
  • $$$0.01 \le r_{u_i,v_i} \le 100:$$$ A real number denoting the exchange rate of the currency $$$u_i$$$ to the currency $$$v_i.$$$
  • $$$0 \le f_{u_i,v_i} \le 1000:$$$ A real number denoting the fee deducted from the exchanged amount.
The following is guaranteed:
  • Along any trajectory $$$\Pi=(p_1,\dots,p_r)$$$ of length $$$r\le n$$$ The product of all rates along the path is less than $$$10^{14}:$$$ $$$$$$ \prod_{i=1}^r r_{p_i,p_{i+1}} \le 10^{14} $$$$$$
  • There is at most one edge between any pair of currencies.
  • Both $$$r_{u_i,v_i},f_{u_i,v_i}$$$ are represented in the form $$$\text{a.b}$$$ where $$$a,b$$$ are integers and $$$0\le b\le 99$$$
Output

Output $$$M:$$$ The minimum integer amount he needs to borrow so that he can make a win. If it is impossible to win any amount of money or Rami needs to borrow more than $$$x$$$, output $$$-1$$$

Examples
Input
2 2 1000
1 2 1.01 10.00
2 1 1.01 10.00
Output
-1
Input
3 4 5000
1 2 0.70 1.00
2 1 1.60 1.00
1 3 0.80 5.00
3 1 2.00 5.00
Output
23
Input
5 5 1000
1 2 1.00 1.00
2 3 1.00 1.00
3 4 1.00 1.00
4 1 1.00 1.00
1 5 10.00 0.00
Output
-1
Input
4 12 1000000000
1 3 0.61 5.74
1 2 1.35 8.86
1 4 0.85 6.00
2 4 0.61 8.23
2 3 0.69 9.45
2 1 0.50 8.71
3 2 1.46 5.04
3 4 1.36 8.00
3 1 0.73 9.89
4 3 0.85 8.34
4 2 0.54 5.99
4 1 1.43 9.60
Output
72
Note
The graph above is a representation of the third test case. Rami needs to borrow only $$$72$$$ to win money. By doing exchanges along the trajectory $$$1\rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1.$$$ He will finish with $$$\sim 72.415768568 \gt 72.$$$ It can be proven that in this case, $$$72$$$ is the smallest amount that will make a win.