# 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

• 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


From AtCoder.com