你来到了一个闯关游戏。
这个游戏总共有 关，每关都有 个通道，你需要选择一个通道并通往后续关卡。其中，第 个通道可以让你前进 关，也就是说，如果你现在在第 关，那么选择第 个通道后，你将直接来到第 关（特别地，如果 ，那么你就通关了）。此外，当你顺利离开第 关时，你还将获得 分。
游戏开始时，你在第 关。请问，你通关时最多能获得多少总分。
第一行两个整数 ，，分别表示关卡数量和每关的通道数量。
接下来一行 个用单个空格隔开的整数 。保证 。
一行一个整数，表示你通关时最多能够获得的分数。
样例输入 1
6 2 2 3 1 0 30 100 30 30
样例输出 1
131
样例解释 1
你可以在第 关选择第 个通道，获得 分并来到第 关；随后再选择第 个通道，获得 分并来到第 关；最后任选一个通道，都可以获得 分并通关。如此，总得分为 。
样例输入 2
6 2 2 3 1 0 30 100 30 -1
样例输出 2
101
样例解释 2
请注意，一些关卡的得分可能是负数。
对于 的测试点，保证 。
对于 的测试点，保证 ；保证 。
对于所有测试点，保证 ；保证 。