Problem1016--加油站

1016: 加油站

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 732  Solved: 180
[Submit] [Status] [Web Board] [Creator:]

Description

一辆汽车加满油后可行驶 n公里。 旅途中有若干加油站。 设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。请对于给定的 nk个加油站位置, 计算最少加油次数。

Input

输入包含多组测试用例。

对于每一组数据,其第1行有2个正整数n1n5000)和 k1k5000)。表示汽车加满油后可行驶 n公里,且旅途中有 k个加油站。接下来的1行中,有 k+1个整数,表示第 k个加油站与第 k-1个加油站之间的距离。第 0个加油站表示出发地,汽车已加满油。第 k+1个加油站表示目的地。

Output

数据输出一行。 如果所对应的输入数据数据可以到达, 将计算的最少加油次数输出。 如果无法到达目的地,则输出NoSolution”。

Sample Input

7  7
1  2  3  4  5  1  6  6

Sample Output

4