Statement

After weeks of training, William finally found out how to win a marathon: by cheating! He teamed up with a skillful driver, his friend Alessandro, and is planning on driving instead of running. The marathon takes place in the beautiful city of Pordenone, which is formed by N intersections and M bidirectional roads. Each road is exactly w_i meters long. The marathon starts at intersection 0 and ends at intersection N-1. Marathoners must go through K checkpoints C_0, C_1, … C_K-1, however, they can run through any route between two consecutive checkpoints. William's plan is the following: (1) he will run from the starting line to the first checkpoints; (2) then he will sneak into Alessandro's car and reach the second checkpoint; (3) next, he will run another piece to the following checkpoint; (4) after that, he will sneak again into Alessandro's car and reach the following checkpoint; (5) … and so on until he reach the finishing line...