Problem1006--「一本通 1.1 练习 2」数列分段

1006: 「一本通 1.1 练习 2」数列分段

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 6  Solved: 3
Submit Status Web Board

Creator:

Description

对于给定的一个长度为 NNN正整数数列 AiA_iAi,现要将其分成连续的若干段,并且每段和不超过 MMM(可以等于 MMM),问最少能将其分成多少段使得满足要求。

Input

第一行包含两个正整数 N,MN,MN,M,表示了数列 AiA_iAi 的长度与每段和的最大值;
第二行包含 NNN 个空格隔开的非负整数 AiA_iAi

Output

输出文件仅包含一个正整数,输出最少划分的段数。

Sample Input

5 6
4 2 4 5 1

Sample Output

3

HINT

对于 20%20\%20% 的数据,有N≤10N\le 10N10
对于 40%40\%40% 的数据,有N≤1000N\le 1000N1000
对于 100%100\%100% 的数据,有 N≤105,M≤109N\le 10^5, M\le 10^9N105,M109MMM 大于所有数的最大值,AiA_iAi 之和不超过 10910^9109

Source/Category


Submit Status