# 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.

- 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.

- 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