← 返回题目列表

AtCoder · s8pc_6_a

A. E869120,穿越时空的人

中文机器翻译题面 查看原题

最高分数:200 点

问题陈述

E869120先生住在高桥王国。
他在 AtCodeer Inc 担任程序员,我们必须参加该公司的一个会议。会议每天定时召开 0.
在高桥王国,有 N 城市,它们被称为城市 1, 城市 2, 城市 3, ..., 城市 N 从西到东。此外,还有一条道路连接各城市 i 和城市 i+1 (1 \leq i \leq N - 1),并采取 A_i 移动分钟。

2031 年 5 月的一天发生了一些事情......他醒来看了看表 - 时间居然到了 0,这是会议时间!
他开会要迟到了。由于AtCodeer Inc.对迟到的要求非常严格,他很有可能被解雇!

但他能够使用一个魔法:TIMELEAP。当他使用它时,时间就会回来 T 分钟。当他在任何城市时,他都可以使用 TIMELEAP。例如,如果 T = 3 他有时使用TIMELEAP 8,那么时间将回到 5.
他想尽量减少TIMELEAP的使用次数。为了不迟到,他应该使用多少个 TIMELEAP?

约束

  • N 是介于 2 和 100 (含)
  • T 是介于 1 和 100 (含)
  • A_i 是介于 1 和 100 (含)

子任务

这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。

  1. (100分):N = 2, T = 1
  2. (100分):无附加限制。

输入

输入由标准输入按以下格式给出:

N T
A_1 A_2 A_3 ... A_{N - 1}

输出

打印 Mr.E869120 应该使用的最小 TIMELEAP 数量。


示例输入 1

2 1
3

示例输出 1

3

例如,如果他进行以下动作,则 TIMELEAP 的数量将为 3.

  1. 最初,E869120先生在城市 1 时间是 0.

  2. 使用 TIMELEAP 3 他在城市时的次数 1。现在时间是 -3.

  3. 从城市搬出 1 前往城市 2。既然需要 3 分钟,现在时间是 0。注:允许到达城市 N 时间 0.


示例输入 2

3 4
5 6

示例输出 2

3

请注意,此测试用例不包含在子任务中 1.