406986: GYM102646 D Team Selection

Timmy is creating a basketball team. In front of him are $$$n$$$ players, lined up. Each one has a skill level $$$a_i$$$, and he must select $$$k$$$ of them in the order that they're lined up in. The $$$j$$$-th player he takes will contribute $$$a_i \cdot b_j$$$ value to the team. Find the maximum possible value.

The first line contains two space-separated integers: $$$n$$$ $$$(1 \leq n \leq 10^3)$$$ and $$$k$$$ $$$(1 \leq k \leq n)$$$. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq 10^5)$$$: the players' skill levels, in the order that they're lined up in.. The third line contains $$$k$$$ space-separated integers $$$b_1, b_2, \dots, b_k$$$ $$$(1 \leq b_i \leq 10^5)$$$.

Print the maximum possible value of the team you can make.

3 2
1 2 3
2 1

7

5 4
5 9 10 3 2
10 10 5 5

215

7 4
1 9 3 8 19 3 2
50 1 9 3

638

In sample 1, Timmy can take players $$$2$$$ and $$$3$$$ to obtain a value of $$$2 \cdot 2 + 3 \cdot 1 = 7$$$.

In sample 2, Timmy can take players $$$2, 3, 4, $$$ and $$$5$$$ to obtain a value of $$$9 \cdot 10 + 10 \cdot 10 + 3 \cdot 5 + 2 \cdot 5 = 215$$$.

In sample 3, Timmy can take players $$$2, 4, 5, $$$ and $$$6$$$.