题目描述

大力水手需要吃菠菜获得能量，现在有n块甲板排成一行，每块板上都有一盒大小不等的菠菜，跳到甲板上就可以获得这盒菠菜，就能获得对应的能量。大力水手首先站在最左边的第1块甲板上，并且直接获得了第1块甲板上菠菜的能量。然后大力水手开始跳跃，每次只能跳到右边相邻的甲板上，并且需要花费能量值为k，当能量不足以跳到下一块甲板，或者已经跳到最后一块甲板上时，结束能量的获取。请计算在此过程中，大力水手曾经获得的最大能量值。

输入格式

共三行。 第一行，1个整数n，表示有n块甲板（1≤n≤105）。 第二行，n个整数，表示第1~n块甲板上菠菜的能量值（0≤能量值≤100），数与数之间以一个空格隔开。 第三行，1个整数k，表示每次跳跃需要花费的能量值k（0≤k≤100）。

输出格式

一行，一个整数，表示过程中曾经获得的最大能量值。

输入输出样例

输入 #1

5
3 4 4 1 2
3

输出 #1

5

提示

样例说明： 共5块甲板，每块甲板上放置的菠菜能量值依次为3、4、4、1、2，每次跳到相邻甲板需要的能量值为3。从第1块甲板直接获得3个能量，然后跳到第2块甲板消耗能量3，又获得了4个能量，所以跳到第2块甲板得到的能量就是4，按此规则依次跳到后面的甲板，再此过程中跳到第3块甲板获得的能量最多为5