ComistryMo和他的小伙伴们最近都很喜欢《葬送的芙莉莲》这一部番，其中有一个角色叫菲伦，灰常滴可爱(●'◡'●)。 但其实她是一个实力雄厚的魔法使，主要攻击手段为普通攻击魔法。在一次控制魔力消耗的训练中，她的师傅芙莉莲给她安排了如下的任务：现在有块石头，下标从开始，每一块石头有一个值为，菲伦需要使用普通攻击魔法来击碎所有的石头，她可以从任意位置开始攻击，击碎第块石头需要消耗菲伦的魔力值。
注意，击碎第块石头之后，后面的石头会向前补齐（下标）。
虽然菲伦的魔力很多，但是她仍然想知道她最少需要消耗的魔力就可以完成这次训练，因此她拜托旅途中认识的ComistryMo来问问大家这个问题的答案是多少。
第一行输入一个正整数 ()，表示石头的数量。
接下来一行个数，第个数表示()，表示第块石头的值。
一行一个整数，表示菲伦最小消耗的魔力量。
样例输入
2 3 2
样例输出
5
保证答案在到 范围内
但其实她是一个实力雄厚的魔法使，主要攻击手段为普通攻击魔法。在一次控制魔力消耗的训练中，她的师傅芙莉莲给她安排了如下的任务：现在有块石头，下标从开始，每一块石头有一个值为，菲伦需要使用普通攻击魔法来击碎所有的石头，她可以从任意位置开始攻击，击碎第块石头需要消耗菲伦的魔力值。