[jag2024国内赛]ジェットコースター 2过山车 2
题目描述
游乐园的过山车每次最多乘坐 (M) 人。当前队列中有 (N) 个团体，从队首到队尾第 (i) 个团体有 (a_i) 人。
每次发车时，工作人员按如下规则从队首开始安排乘客：
- 若队列为空，或者队首团体人数大于当前车厢剩余座位数，则发车，本次运行结束；
- 否则，将队首团体全员安排上车；
- 回到步骤 1。
一直重复直到队列为空。
现在允许至多进行一次操作：交换队列中一对相邻团体的位置。请问最优操作后，把所有乘客送完所需的最少运行次数是多少。
输入格式
输入包含不超过 (50) 个数据集。
每个数据集格式如下：
N M
a1 a2 ... aN
(2\le N\le 2\times 10^5)，(1\le M\le 10^9)。
(1\le a_i\le M)。
所有数据集的 (N) 之和不超过 (2\times 10^6)。
输入以 0 0 结束。
输出格式
对每个数据集，输出最少运行次数。
样例输入
9 5
3 3 2 2 3 3 2 2 2
6 20
9 15 7 18 5 6
0 0
样例输出
5
4