Page not loading? Try clicking here.
Placeholder

#5092

정올이의 모의고사 1s 128MB

Problems

정올이는 정보올림피아드를 앞두고 모의고사를 보려고한다.

 

해당 모의고사는 총 T분동안 진행되며 N개의 문제가 나온다. 모의고사가 진행되는 동안 아무 때나 소스 코드를 제출할 수 있다.

i번 문제를 t분에 맞춘 경우에는 Mi-t*Pi 점을 받게 된다. 이 테스트에 응시한 정올이가 i번 문제를 푸는데 걸리는 시간은 Ri분이다.

이때, 정올이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.​


Input

첫째 줄에 N과 T가 주어진다. (1 ≤ N ≤ 50, 1 ≤ T ≤ 100,000)

 

둘째 줄에는 M_i가 N개, 셋째 줄에는 P_i가 N개​, 넷째 줄에는 R_i가 N개​가 주어진다. (1 ≤ M_i, P_i, R_i ≤ 100,000)​ 


Output

정올이가 얻을 수 있는 점수의 최댓값을 출력하시오.


Example #1

1 74

502

2

47
408

Example #2

2 40000

100000 100000

1 100000

50000 30000
0

Example #3

3 75

250 500 1000

2 4 8

25 25 25
1200

Example #4

3 30

100 100 100000

1 1 100

15 15 30
97000


Source

data:klee
You must sign in to write code.