犇犇轮值成为一名ACCSP集训队队长，正在组织队员们进行编程训练。

已知集训队每年年初都会招新生，新同学入队后都会参与接下来的 D 年的训练，然后退役。换句话说，每位队员从加入集训队的第 1 年开始，会一直努力奋斗到第 D 年结束，然后在第 D+1 年年初退出集训队。

由于种种原因，每年队员们训练的题目套数并不相同。但犇犇知道在接下来的 N 年里，第 i 年集训队会组织 A_i 场编程训练，也就是说这一年需要犇犇准备 A_i 套现役队员们都没有做过的题目拿来当作训练题。

由于学习编程的同学们记忆力都超强，只要某位队员做过了一套题，那么在这位队员退役之前，这套题都不能够拿来重新当作训练题。

但对于一套题目来说，即使这套题此前已经被使用过，只要曾经做过这套题的队员都已经退役了，那就可以重新拿出来当作训练题用。

现在，请问犇犇需要提前准备至少多少套不同的题目，才能够保证这 N 年的训练都能够正常举行，也就是没有任何队员会做到已经做过的题目？

第一行包含两个正整数 N, D，分别表示总年数以及每位队员从入队到退役需要经过的年数。

第二行包含 N 个正整数 A_1, A_2, \cdots, A_N，分别表示每年需要准备的题目套数。

一个整数，表示需要准备的题目数量。

数据范围

对于 20\% 的数据：N \le 20

对于 40\% 的数据：N \le 1\,000

对于 100\% 的数据：1 \le D \le N \le 300\,000，1 \le A_i \le 1\,000\,000