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 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 S[0], S[1] ... S[K-1], however, they can run through any route between two consecutive checkpoints.