Candy Contribution

아직 제출이 없습니다시간 제한3초메모리 제한1024 MB

문제

While you were out travelling, you won the lottery. As it happened, the top prize of this lottery was not cash, but candies! Now you are stuck with a big pile of candies which you would like to take home. Fortunately, you have been able to acquire a truck, so now all you have to do is drive home.

Going from one country to another with such a big pile of candies in your truck is not allowed without paying some taxes. And because everybody likes candies, you are allowed to pay these taxes with candies.

After searching a bit on the internet, you have found a list that tells you exactly which borders you can cross with a truck and for each such border what percentage of tax you have to pay to cross it. You cannot pay with fractional candies and the candies are quite nice, so customs will always round up. You only have to pay taxes on the number of candies you bring across the border.

What is the maximum number of candies you can bring home?

입력

The input consists of:

  • One line containing two integers nn (2n11052\leq n\leq 1\cdot 10^5), the number of countries, and mm (1m21051 \leq m \leq 2\cdot 10^5), the number of borders. 
  • One line containing three integers ss (1sn1\leq s\leq n), the country where you won the lottery, tt (1tn1 \leq t \leq n, tst\neq s), your home country and cc (1c1091\leq c \leq 10^9) the number of candies you won in the lottery.
  • Then follow mm lines containing three integers u,vu, v (1u,vn1\leq u, v \leq n, uvu\neq v) and pp (0p1000 \leq p \leq 100) where pp is the percentage of tax you have to pay when travelling from country uu to vv or vice versa.

It is guaranteed you can drive home with your truck, and that each pair of countries is listed at most once.

출력

Output the maximum number of candies you can arrive home with.