Fruit Harvest

View as PDF

Submit solution

Points: 0.60 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Little MofK has ~n~ gardens, each garden grows one of ~k~ types of fruits: the ~i~-th garden grows fruit type ~t_i~ and has ~a_i~ fruits.

To make cakes, MofK's mother sends him to harvest fruits. MofK will choose a segment ~[l..r]~ and pick all the fruits in those gardens. Each cake requires one fruit of each type, so if MofK picks ~x_1, x_2, \ldots, x_k~ fruits of each type, his mother can make ~\min(x_1, x_2, \ldots, x_k)~ cakes, and the remaining fruits will be given to MofK. In other words, MofK will eat ~x_1 + x_2 + \ldots + x_k - k \cdot \min(x_1, x_2, \ldots, x_k)~ fruits.

Help MofK choose the segment ~[l..r]~ to eat as many fruits as possible!


The first line contains two positive integers ~n~ and ~k~ (~1 \le n, k \le 3 \cdot 10^5~) — the number of gardens and the number of fruit types.

The next line contains ~n~ positive integers ~t_1, t_2, \ldots, t_n~ (~1 \le t_i \le k~) — the type of fruit grown in the ~i~-th garden.

The last line contains ~n~ positive integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the number of fruits grown in the ~i~-th garden.


Print a single positive integer: the maximum number of fruits that MofK can be given.


Subtask Points Constraints
~1~ 500 ~n, k \le 500~
~2~ 500 ~n, k \le 2000~
~3~ 1250 no additional constraints
Total 2250

Sample Input 1

4 3
2 1 2 3
6 3 3 4

Sample Output 1


Sample Input 2

4 1
1 1 1 1
3 2 6 2

Sample Output 2



In the first sample test, we can choose the segment ~[1, 3]~; then, the number of fruits MofK picks are ~[3, 9, 0]~, so the number of fruits that MofK can eat is ~3 + 9 + 0 - 3 \cdot 0 = 12~.

In the second sample test, since there is only one type of fruit, all the fruits that MofK picks will be used to make cakes, and MofK will not have any fruits to eat. :(


Please read the guidelines before commenting.

There are no comments at the moment.