Harry has drunk liquid luck and won a ticket to amusment park. He can stay there for n days. and there are m games he can play in the park, if he wins the ith game he gets v[i] points. each day he can only play the ith game once. Chances of winning in ith game is e[i]. the chances decrease each day by d[i]. But because of liquid luck, harry can win any game as long as the chance is > 0. Harry must rest at least 1 day in k consecutive days. As soon as Harry rests, his chances are back to what they were when he started. What is the maximum number of points Harry can gather?
example:
in:
5 5 3
1 2 3 4 5
2 3 5 1 2
1 1 2 1 1
out:
52
in:
6 3 3
3 4 2
14 18 7
6 18 0
out:
32
first line 3 space separated integers n,m,k
second line: space separated integers v[i]
third line: space separated integers e[i]
last line: space separated integers d[i]