Get Min Requests (Server Reliability Drill)

At the start of each second, every server still alive contributes requests equal to its request; in the same second, choose one alive server and reduce its health by k, and it dies immediately once health≤0. After all servers have died, exactly 1 more request is sent. Arrange the attack order to minimize the total number of requests.

输入格式

The first line contains n k (1≤n≤100000, 1≤k≤5000); the second line contains n request values, and the third line contains n health values, all 1..5000.

输出格式

Output a single integer answer.

样例 1

输入：

2 3
3 4
4 6

输出：

21

样例 2

输入：

1 1
1
1

输出：

2

样例 3

输入：

2 1
5 1
1 3

输出：

10

样例说明

Example 1: first attack the server with request=4 twice in a row, then attack the other one twice; the requests are 7+7+3+3+1=21. Example 2: 1 request in that second plus the final request 1, 2 in total. Example 3: shut down the request=5 server first, then keep handling the other one for three seconds, for a total of 6+1+1+1+1=10.