App

Time limit1sMemory limit128 MB

Summary

Choose a subset of active apps to deactivate whose freed memory is at least M while minimizing the total deactivation cost.

Level: Medium6 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

While using a smartphone we run many apps. Usually only one app is visibly "running" on the screen, but many more are "active" without being shown. An app being active means that, even if it is not visible, its most recent state is kept in main memory. The reason for keeping it there even when it is not currently running is so that, when the user reopens a previously used app, its last state can be read back from main memory to finish preparing to run quickly.

However, a smartphone's memory is limited, so if every app that was ever launched is kept active in main memory, memory shortages arise easily. When there is not enough memory to launch a new app, the operating system has no choice but to select some active apps and remove them from memory. This process is called "deactivating" an app.

When memory runs low, deactivating active apps at random until enough memory is freed is not a good approach, because relaunching a deactivated app takes extra time. Write a program that solves this deactivation problem smartly.

Suppose $N$ apps $A_1, \dots, A_N$ are currently active. Each app $A_i$ is using $m_i$ bytes of memory. Let $c_i$ be a numeric value (time, etc.) for the extra cost of relaunching app $A_i$ after it has been deactivated. The user wants to launch a new app $B$ and needs $M$ additional bytes of memory. That is, you must deactivate some of the active apps $A_1, \dots, A_N$ to free at least $M$ additional bytes. Among all such ways, find the one that minimizes the sum of the costs $c_i$ of the deactivated apps, and output that minimum cost.

Input

The input consists of three lines. The first line contains two integers $N$ and $M$ separated by a space. The second line contains $N$ integers $m_1, \dots, m_N$ separated by spaces, the number of bytes of memory used by the active apps. The third line contains $N$ integers $c_1, \dots, c_N$ separated by spaces, the cost of deactivating each app.

Constraints: $1 \le N \le 100$ , $1 \le M \le 10\,000\,000$ , $1 \le m_i \le 10\,000\,000$ , $0 \le c_i \le 100$ , and $M \le m_1 + m_2 + \dots + m_N$ .

Output

Print, on a single line, the minimum cost of deactivating apps to free $M$ bytes.

Examples4

Example 1
Input
```
5 60
30 10 20 35 40
3 0 3 5 4
```
Expected output
```
6
```
Example 2
Input
```
1 1
1
5
```
Expected output
```
5
```
Example 3
Input
```
3 15
10 20 30
0 0 0
```
Expected output
```
0
```
Example 4
Input
```
4 10
10 10 10 10
4 3 2 1
```
Expected output
```
1
```