Dynamic Programming - Problem Collection

2019-2-26 created by AD1024

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

• The first line contains two numbers $N$ and $K$ ($1 \leq N \leq 20$, $1 \leq K \leq 6$);
• The second line contains a number with $N$ digits.

Output

• A single line of the maximum product you can get by dividing the number into $K$ parts.

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

• the first line includes two positive integers $N$, $M$. ($1 \leq N \leq 120$, $1 \leq M \leq 300$);
• the second line contains $N$ integers denotes the numbers on the cards;
• the third line contains $M$ integers, the $i^{th}$ number stands for the point you can get by letting the bot stop at the $i^{th}$ grid.

Output

• A single integer stands for the maxumum point you can get.

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