The cows are heading back to the barn at the end of a long day, feeling both tired and hungry.

The farm consists of N pastures (2 \leq N \leq 50,000), conveniently numbered 1 \dots N. The cows all want to travel to the barn in pasture N. Each of the other N-1 pastures contains a cow. Cows can move from pasture to pasture via a set of M undirected trails (1 \leq M \leq 100,000). The ith trail connects a pair of pastures a_i and b_i, and requires time t_i to traverse. Every cow can reach the barn through a sequence of trails.

Being hungry, the cows are interested in potentially stopping for food on their way home. Conveniently, K of the pastures contain tasty haybales (1 \leq K \leq N), with the ith such haybale having a yumminess value of y_i. Each cow is willing to stop at a single haybale along her trip to the barn, but only if the amount of time this adds to her path is at most the yumminess of the haybale she visits. Note that a cow only "officially" visits at most one haybale for dining purposes, although it is fine if her path takes her through other pastures containing haybales; she simply ignores these.

Problem credits: Dhruv Rohatgi

#4084 upload 3 done 3 how_to_reg 3

Fine Dining timer 2s memory 512MB

#4084

Fine Dining 2s 512MB