Cutting Trees

Time limit2sMemory limit512 MB

Summary

Cut at most M trees per evening with distinct machines to exactly D_i meters, and find the minimum total height after T days.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Limits

$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$

Hint

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.

Examples5

Example 1
Input
```
2 1
4 7
7 1
7
1
```
Expected output
```
15
```
Example 2
Input
```
3 3
3 1 2
1 1 1
7 7 7
2
```
Expected output
```
12
```
Example 3
Input
```
2 3
100 50
75 30
200 100 50
2
```
Expected output
```
130
```

Example 4

Input

12 4
7 10 1 7 5 4 11 5 7 9 10 8
1 3 4 10 2 1 6 4 8 7 5 10
7 1 5 10
3

Expected output

Example 5

Input

4 6
35 45 32 8
2 25 31 5
29 28 3 11 28 37
8

Expected output