April Fools' Problem (medium)

4000ms

262144K

Description:

The marmots need to prepare k problems for HC² over n days. Each problem, once prepared, also has to be printed.

The preparation of a problem on day i (at most one per day) costs a_i CHF, and the printing of a problem on day i (also at most one per day) costs b_i CHF. Of course, a problem cannot be printed before it has been prepared (but doing both on the same day is fine).

What is the minimum cost of preparation and printing?

Input:

The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 2200). The second line contains n space-separated integers a₁, ..., a_n ( $\text{[math]}$ ) — the preparation costs. The third line contains n space-separated integers b₁, ..., b_n ( $\text{[math]}$ ) — the printing costs.

Output:

Output the minimum cost of preparation and printing k problems — that is, the minimum possible sum a_i₁ + a_i₂ + ... + a_{i_k} + b_j₁ + b_j₂ + ... + b_{j_k}, where 1 ≤ i₁ < i₂ < ... < i_k ≤ n, 1 ≤ j₁ < j₂ < ... < j_k ≤ n and i₁ ≤ j₁, i₂ ≤ j₂, ..., i_k ≤ j_k.

Sample Input:

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

Sample Output:

Note:

In the sample testcase, one optimum solution is to prepare the first problem on day 1 and print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8.

Informação

Provedor Codeforces

Código CF802N