우리는 스마트폰을 사용하면서 여러 개의 앱을 동시에 실행하곤 한다. 대개의 경우 이들을 사용하고 난 후에 종료하지 않기 때문에, 이러한 앱들은 백그라운드에서 실행 중인 상태로 남게 된다.

따라서 실행 중인 앱들이 차지하는 메모리 용량의 총합이 스마트폰의 주기억장치 용량을 초과하는 상황이 발생할 수 있다.

스마트폰의 운영체제는 새로운 앱을 실행시키기 위해 필요한 메모리 공간을 확보하고자, 현재 백그라운드에서 실행 중인 앱들 중 일부를 비활성화(종료)시키는 결정을 내려야 할 수 있다.

현재 활성화되어 있는 앱 \(A_1, \dots, A_N\) 중에서 몇 개를 비활성화하여 \(M\) 바이트 이상의 메모리를 추가로 확보해야 한다.

각 앱 \(A_i\)는 \(m_i\) 바이트만큼의 메모리를 사용하고 있으며, 이를 비활성화했을 때 \(c_i\)만큼의 비용(부담)이 발생한다.

여러분은 앱들을 비활성화했을 경우 발생하는 비용 \(c_i\)의 합을 최소화하면서, 필요한 메모리 \(M\) 바이트 이상을 추가로 확보할 수 있는 방법을 찾는 프로그램을 작성하시오.

입력

첫 줄에는 정수 \(N\)과 \(M\)이 공백문자로 구분되어 주어진다.

둘째 줄에는 현재 활성화되어 있는 앱 \(A_1, \dots, A_N\)이 사용 중인 메모리의 바이트 수인 \(m_1, \dots, m_N\)이 공백문자로 구분되어 주어진다.

셋째 줄에는 각 앱을 비활성화했을 경우의 비용 \(c_1, \dots, c_N\)이 공백문자로 구분되어 주어진다.

출력

필요한 메모리 \(M\) 바이트 이상을 확보하기 위한 앱 비활성화 비용의 최솟값을 한 줄에 출력한다.

제한사항

• \(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\) 바이트를 확보할 수 있는 입력만 주어진다.

예제 입력 1

5 60
30 10 20 35 40
3 0 3 5 4

예제 출력 1

6

예제 입력 2

3 10
5 5 5
1 2 3

예제 출력 2

3

출처

2013 지역본선 고등