公元 2242 年，您是星际勘探舰“奥德赛号”的舰长，正在执行一项穿越未知小行星带的危险任务。 远程扫描显示，前方有一条由 颗小行星组成的直线路径，每一颗都蕴藏着宝贵的能量水晶。 您的任务是规划航线，最大限度地补充舰船的能量储备。 您将要穿越的星系包含 颗小行星，编号从 到 。您的舰船只能沿着编号递增的方向前进，无法后退。 初始状态 : 您的舰船携带有 个单位的初始能量。 航行消耗 : 从当前位置航行到下一颗小行星，需要消耗 个单位的能量。如果能量为 ，舰船将无法启动，无法航行到新的小行星。 能量采集 : 您装备了一台高能水晶采集器，但由于能源核心的限制，在整个任务中最多只能使用 次。每颗小行星最多只能被采集一次。采集小行星 上的水晶，可以为舰船瞬间补充 个单位的能量。 您的目标是，在整个勘探任务的任意时刻，舰船所能达到的**最大能量值**是多少？ 请注意，您可以选择不登陆任何小行星。

输入描述:

第一行包含三个正整数 ()，由空格隔开。第二行包含 个整数 ()，代表每颗小行星上蕴含的能量水晶数量，由空格隔开。

输出描述:

一个整数，表示在整个任务过程中，舰船能达到的最大能量值。

备注:

本题由牛友@Charles 整理上传