As most fairy tales said, unfortunately, our poor princess is trapped in a castle by some bad guys again.
Simple word, we need save her again, because she is so beautiful and graceful that we love her so much. Our country was composed of N cities and M undirected roads, the princess was in the city A, and we were in city 0, the capital. Obviously, only we arrive at the city A first can we save the princess.
However, it’s not a shortest path problem because we had extremely enough time to spend among the roads. What matters was whether we could arrive at the city A.
Perhaps a strange problem, but it’s reasonable because we need food and water while travelling from one city to another, or we just would be died before we can see the princess. To make the situation less complicated, we assumed we always consumed two units of food and one unit of water when we were walking, just like a coefficient multiply the distance we had walked.
But the condition left for us is a little annoyed. As our country was very poor, we could only purchase the food in the capital. What’s more, at any time, the sum of food units and water units we carried can’t exceed the capacity S.
Oh, don’t be despair, please. Also some not too bad news was here. We could rest and collect water as much as possible at any city, and in each city, there were plenty of storages to store food for our later use.
Now, to save our lovely and pitiful princess, how much food we have to purchase in the capital at least?