题目描述

The chessboard of the Turtle Chess is a row of NN squares, each with a fraction (not a negative integer). Grid 1 is the only starting point, NN is the end, and the game requires the player to control a turtle piece from the starting point to the end.

MM crawling cards in Turtle Chess are divided into 4 different types (MM cards do not necessarily contain all 44 types of cards, see examples), and each type of card is marked with one of the four numbers of 1, 2, 3, 4, indicating that after using this card, the Turtle Chess Piece will crawl forward with the corresponding number of squares. In the game, the player needs to select one of the crawling cards from all the crawling cards that have not been used before, and control the number of tiles corresponding to the advance of the turtle pieces, and each card can only be used once.

In the game, the turtle pieces automatically get the score of the starting square, and each time a grid is reached in the subsequent crawl, the corresponding score of the grid is obtained. The player's final game score is the sum of all the squares that the turtle pieces have reached from start to finish.

Obviously, using different crawling card usage orders will make the final game score different, and Bob wants to find a card usage order that makes the final game score the most.

Now, tell you the score of each grid on the board and all the crawling cards, can you tell Bob how many points he can get at most?

输入格式

A large string of numbers

输出格式

The scores he will get the most

样例

9 5 
6 10 14 2 8 8 18 5 17 
1 3 1 2 1

73

提示

A very classic title, taken from the Luogu, English version

By TOP