An exam consists of N questions. The marks of the N questions are m1, m2, m3, .. mN respectively.
Jam is giving the exam and he wants to maximise his number of marks.
However he takes some time to solve each question. The time taken by him to solve the questions are t1, t2, t3, .. tN respectively.
The exams lasts for a total of time T.
But Jam's teacher is very smart and she knows that Jam will find out a way to get maximum marks. So, to confuse Jam, she also puts up a bonus offer for him -
The offer is that Jam can select a question for which he can double the marks awarded for that question.
Now, Jam is indeed confused. Help him find out the maximum number of marks he can gain.

Input

The first line contains a single integer N, that represents the number of questions.
Second line contains a single integer T, the total time for which the exam takes place.
Third line contains N space-separated integers
m1, m2, m3, ... mN, where mi represents marks assigned to the i^th question.
Fourth line contains N space-separated integers
t1, t2, t3, ... tN, where ti represents time taken to solve the i^th question.

Output
Output a single integer, that is the maximum number of marks Jam can achieve.

Constraints
1<=N<=1000
1<=T<=10000
1<=mi<=100000
1<=ti<=10000

Example
Input:
3
10
1 2 3
4 3 4

Output:
8

见题面

见题面