Cutting Trees

Subin grows N trees in the garden. Tree i is $H_i$ meters tall right now and grows $A_i$ meters every morning.

Subin owns M cutting machines. Machine i picks one tree whose height is greater than $D_i$ meters and cuts that tree down to exactly $D_i$ meters. A tree whose height is at most $D_i$ meters cannot be cut by machine i.

Every evening Subin picks some trees and cuts them. Picking no tree at all is allowed. Two conditions must hold.

• Each tree is cut at most once on a given day.
• Each machine can be used at most once on a given day.

So the trees cut on the same evening are paired with distinct machines, one machine per tree.

A day consists of the morning growth followed by the evening cutting. Write a program that finds the smallest possible sum of the tree heights after T days.

The first line contains the number of trees N and the number of machines M, separated by a space.

The second line contains $H_1, H_2, \ldots, H_N$ separated by spaces.

The third line contains $A_1, A_2, \ldots, A_N$ separated by spaces.

The fourth line contains $D_1, D_2, \ldots, D_M$ separated by spaces.

The fifth line contains T.

Print the smallest possible sum of the tree heights after T days, on one line.

• $1 \le N, M \le 150$
• $0 \le H_i, A_i \le 10000$
• $0 \le D_i \le 10000$
• $1 \le T \le 150$

Suppose there are 2 trees. Tree 1 is 4 meters tall and grows 7 meters a day, tree 2 is 7 meters tall and grows 1 meter a day. There is a single machine with $D_1 = 7$, and T is 1.

After the first morning, tree 1 is $4 + 7 = 11$ meters tall and tree 2 is $7 + 1 = 8$ meters tall. Cutting tree 1 down to 7 meters in the evening leaves a height sum of 15, and no smaller sum is reachable.