앱

스마트폰에서는 여러 앱(App)을 실행하며 사용한다. 화면에 '실행 중'으로 보이는 앱은 보통 하나지만, 화면에 보이지 않는 상태로도 많은 앱이 '활성화'되어 있다. 앱이 활성화되어 있다는 것은 화면에 보이지 않더라도 직전 상태가 메인 메모리에 남아 있다는 뜻이다. 현재 실행 중이 아니어도 이렇게 메모리에 남겨 두는 이유는, 사용자가 이전에 쓰던 앱을 다시 열 때 직전 상태를 메모리에서 곧바로 읽어 실행 준비를 빠르게 마치기 위해서다.

그러나 스마트폰의 메모리는 한정되어 있어, 한 번이라도 실행한 앱을 모두 활성화한 채로 남겨 두면 메모리가 금세 부족해진다. 새 앱을 실행할 메모리가 모자라면 운영체제는 활성화된 앱 중 몇 개를 골라 메모리에서 지울 수밖에 없다. 이 과정을 앱의 '비활성화'라고 한다.

메모리가 부족할 때 활성화된 앱을 아무렇게나 골라 비활성화하는 것은 좋지 않다. 비활성화한 앱을 다시 실행하려면 그만큼 시간이 더 들기 때문이다. 이 비활성화 문제를 똑똑하게 푸는 프로그램을 작성하자.

현재 $N$개의 앱 $A_1, \dots, A_N$이 활성화되어 있다. 앱 $A_i$는 각각 $m_i$ 바이트의 메모리를 사용하고 있다. 또한 앱 $A_i$를 비활성화한 뒤 다시 실행할 때 추가로 드는 비용(시간 등)을 수치로 나타낸 값을 $c_i$라고 하자. 사용자가 새 앱 $B$를 실행하려는데 메모리가 $M$ 바이트 더 필요하다. 즉, 활성화된 앱 $A_1, \dots, A_N$ 중 몇 개를 비활성화하여 $M$ 바이트 이상의 메모리를 추가로 확보해야 한다. 확보하는 여러 방법 중 비활성화한 앱들의 비용 $c_i$의 합이 최소가 되도록 하는 방법을 찾아, 그 최소 비용을 구하라.

입력은 세 줄로 이루어진다. 첫 줄에는 정수 $N$과 $M$이 공백으로 구분되어 주어진다. 둘째 줄에는 $N$개의 정수 $m_1, \dots, m_N$이 공백으로 구분되어 주어지며, 이는 활성화된 앱들이 사용 중인 메모리의 바이트 수다. 셋째 줄에는 $N$개의 정수 $c_1, \dots, c_N$이 공백으로 구분되어 주어지며, 이는 각 앱을 비활성화할 때의 비용이다.

제약은 다음과 같다. $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$이며, $M \le m_1 + m_2 + \dots + m_N$이다.

$M$ 바이트를 확보하기 위해 앱을 비활성화하는 데 드는 최소 비용을 한 줄에 출력한다.