|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초 (추가 시간 없음)||1024 MB||58||38||35||66.038%|
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:
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.
4 4 1 4 1000 1 2 25 2 4 10 1 3 4 3 4 30
5 5 1 5 6 1 2 17 2 5 19 1 3 1 3 4 1 4 5 1