UOJ Logo Zijian Online Judge

ZOJ

Statistics

小学的校长准备找一辆大巴,这样老师们就可以带着大家去郊游了。

如果大巴的油箱容量是 $m$,那么在满油的状态下大巴可以开 $m$ 公里。

郊游的路线是一个环,上面有 $n$ 个目标点,第 $i$ 个目标点到第 $i+1$ 个目标点(如果 $i=n$ 的话就是到第 $1$ 个地点) 的距离为 $l_i$ 公里。

校长可以任意确定大巴的起点,然后大巴会绕这个环一圈,最后回到起点结束。

在路上有可能大巴需要加油,大巴可以在任意一个目标点加油。为了不打扰同学们的旅行,法珞希望加油的次数尽可能少。

校长有 $k$ 种可选的大巴,第 $i$ 个大巴的油箱容量是 $m_i$。对于每一种大巴,校长想知道,它是否能完成这次旅行(不会在半路没油),如果能的话,最少需要加多少次油。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $l_i$。

第三行 $k$ 个整数 $m_i$。

输出格式

对于每一种大巴,如果它不能到达终点,输出 "Invalid"(不含引号) ,否则输出最少的加油次数。

样例一

input

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

output

4
Invalid
3
2

样例二

见样例数据下载

限制与约定

对于 $20\texttt{%}$ 的数据,$1 \le n \le 1000$。

对于另外 $20\texttt{%}$ 的数据,$1 \le k \le 5$。

对于另外 $20\texttt{%}$ 的数据,$1 \le n \le 10^5$。

对于 $100\texttt{%}$ 的数据,$1 \le n \le 10^6$,$1 \le k \le 100$,$1 \le m_i,\sum l_i \le 10^9$。

时间限制:$4\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载