[Poi2014]Around the world

时间限制：80s 空间限制：24MB

题目描述

After trying hard for many years, Byteasar has finally received a pilot license. To celebrate the fact, he intends to buy himself an airplane and fly around the planet 3-SATurn (as you may have guessed, this is the planet on which Byteotia is located). Specifically, Byteasar plans to fly along the equator. Unfortunately, the equator is rather long, necessitating refuels. The flight range (on full tank) of each aircraft is known. There is a number of airports along the equator, and a plane can be refueled when it lands on one. Since buying an airplane is a big decision, Byteasar asks your help. He is about to present you with a list of different plane models he is considering. Naturally, these differ in their flight range. For each plane model, he would like to know the minimum number of landings (including the final one) he would have to make in order to complete the journey. Note that for each airplane model, the journey may start at a different airport.

通过几年的努力，Byteasar最终拿到了飞行员驾驶证。为了庆祝这一事实，他打算买一架飞机并且绕Byteotia星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场，所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定，Byteasar决定寻求你的帮助。他将会让你模拟不同的飞行路线。自然这些飞机一次能走的航程是不同的。对于每次模拟，他想要知道最少需要降落多少次（包括最后一次）。需要注意的是起点可以任意选取。

输入格式

The second line contains N positive integers L1,L2…Ln(L1+L2+..+Ln<=10^9), separated by single spaces, specifying the distances between successive airports along the equator. The number Li is the distance between the i-th and (i+1)-st (or N-th and first if i=N) in kilometers.

第一行有两个正整数n和s（2<=n<=1000000，1<=s<=100）分别代表赤道上面的飞机场个数和询问的航班数第二行有n个正整数L1,L2…Ln（L1+L2+…+Ln<=10^9）按顺序给出了n个相邻机场之间的距离。其中Li是第i个与第i+1个机场之间的距离，Ln是第n个和第1个之间的距离。第三行给出了n个正整数di（1<=di<=L1+L2+…+Ln）。其中di代表第i个飞机一次能走的航程。

输出格式

Your program should print S lines to the standard output: the i-th of these should contain a single integer, namely, the minimum lumber of flight segments (and thus also landings) necessary to fly the i-th airplane around the planet 3-SATurn along the equator, starting at an airport of choice, or the word NIE (Polish for no) if it is impossible to complete the journey with this airplane.

输出s行每行一个整数代表最小降落次数或者一个字符串“NIE”代表不能到达

样例输入

6 4
2 2 1 3 3 1
3 2 4 11

样例输出

4
NIE
3
2

提示

The thick solid line shows the optimal journey of the plane with flight range 4, whereas the dashed line the optimal journey of the plane with flight range 3.

题目来源

没有写明来源