Journey with Pigs

Time limit2sMemory limit64 MB

Summary

Given pig weights and per-village net price coefficients, assign pigs to villages one-to-one to maximize total revenue (sort and multiply greedily).

Level: Easy3 of 10
Topics: Greedy, Sorting, Math
Solved: No attempts yet

Problem

Farmer John runs a pig farm near town A and wants to visit a friend who lives in town B. On the road to town B he passes n small villages, so he decides to make some money along the way. He sets out with n pigs and sells exactly one pig in each village he passes.

Pork prices differ from village to village: in the j-th village people buy pork at p_j rubles per kilogram. The distance from town A to the j-th village along the road is d_j kilometers.

The pigs have different weights. Transporting one kilogram of pork over one kilometer of road costs t rubles in extra fuel. So carrying a pig of weight w over a distance d costs w·d·t rubles, while selling it in the j-th village earns w·p_j rubles; the net earning from that pig is therefore w·(p_j − d_j·t) rubles.

John must sell exactly one pig in each village — that is, he assigns pigs to villages one-to-one and sells them all. Choose the assignment that maximizes the sum of the net earnings and report the maximum total amount of money John can earn.

Input

The first line contains two integers n (1 ≤ n ≤ 1000) and t (1 ≤ t ≤ 10^9). The second line contains n integers w_i (1 ≤ w_i ≤ 10^9), the weights of the pigs. The third line contains n integers d_j (1 ≤ d_j ≤ 10^9), the distances from town A to the villages. The fourth line contains n integers p_j (1 ≤ p_j ≤ 10^9), the pork prices in the villages.

Output

Print a single integer: the maximum total amount of money John can earn when he sells exactly one pig in each village. Because every pig must be sold, this value can be negative.

Examples4

Example 1
Input
```
3 1
10 20 15
10 20 30
50 70 60
```
Expected output
```
1900
```
Example 2
Input
```
1 1
5
2
10
```
Expected output
```
40
```
Example 3
Input
```
2 100
1 2
10 20
5 7
```
Expected output
```
-3983
```
Example 4
Input
```
4 2
5 5 5 5
1 2 3 4
10 20 30 40
```
Expected output
```
400
```