6482: 闯关游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

你来到了一个闯关游戏。

这个游戏总共有  关,每关都有  个通道,你需要选择一个通道并通往后续关卡。其中,第  个通道可以让你前进  关,也就是说,如果你现在在第  关,那么选择第  个通道后,你将直接来到第 + 关(特别地,如果 +,那么你就通关了)。此外,当你顺利离开第  关时,你还将获得  分。

游戏开始时,你在第 0 关。请问,你通关时最多能获得多少总分。

Input

第一行两个整数 ,分别表示关卡数量和每关的通道数量。

接下来一行  个用单个空格隔开的整数 0,1,1。保证 1

接下来一行  个用单个空格隔开的整数 0,1,1。保证 105

Output

一行一个整数,表示你通关时最多能够获得的分数。

Sample Input Copy

6 2 
2 3
1 0 30 100 30 30

Sample Output Copy

131

HINT

对于 20% 的测试点,保证 =1

对于 40% 的测试点,保证 20;保证 2

对于所有测试点,保证 1104;保证 1100