Dynamic Programming - Problem Collection

2019-2-26 created by AD1024
DP

Intro

Here are some interesting problems you can try to solve it. Note: They are not actually hard.

Divide the number

Statement

You are given a number with $N$ digits. Now, I ask you to divide the number into $K$ numbers such that the product of these numbers is maximized.

Input

Output

Sample

Input:

4 2
1231

Output:

62

Sum it up

Statement

There are $N$ command cards. A number $k$ on a card satisfies that $1 \leq k \leq 4$. You can use these command cards to send command to a bot on a track and let the bot step $k$ steps foward, and you can use these cards in any order you want to. The track is divided into $M$ grids, by stopping at a grid at $i^{th}$ position, you will get $a_i$ points. Find the maximum point you can get.

Input

Output

Note: the number along the way bot passes does not count to the total sum. Only the numbers at where exactly it stops at count

Sample

Input

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

Output

73

Others

From AtCoder.com