渡船等候

题目描述

渡船连续发船N次，每次最多搭载C人。第i次发船前先有a_i人加入等候队伍，再立即让尽可能多的人登船。未上船的人留到下次；本次没用完的空位不能留到下次。起初无人等候。求每次发船后等候人数的最大值，以及最后一次发船后等候人数。

输入格式

第一行N、C；第二行按时间顺序给出N个到达人数。

输出格式

输出最大等候人数和最终等候人数。

样例 1

输入

4 5
3 9 1 8

输出

4 3

说明

各次发船后等候0、4、0、3人。

样例 2

输入

1 5
0

输出

0 0

说明

没有乘客。

数据范围

• 1≤N≤100000；1≤C≤10^9。
• 0≤a_i≤10^9，允许多次为0。