문제1271--지하철을 빠르게 빠르게 HARD

1271: 지하철을 빠르게 빠르게 HARD

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 84  통과: 2
[제출] [채점기록] [묻고답하기] [만든사람:]

문제 설명

서울 지하철 2호선은 순환선이다. 순환선의 어떤 두 열차는 속력 차이가 많이 날 때, 열차 간 간격이 좁아져서 부딪힐 위험이 생긴다. 그래서 2호선의 모든 열차는 순환선을 돌고 있는 열차 중 가장 느린 열차에 속력을 맞출 수밖에 없고, 그게 결국 2호선의 속력이 된다.
2호선에는 N개의 열차가 있다. 모든 열차는 생산 연도도 다르고, 관리 상태도 다르기 때문에 낼 수 있는 최대 속력과 수리(혹은 개조) 비용이 각각 다르다. 각 열차의 현재 최대 속력 Si와 1원 당 속도 증가량 Vi가 주어진다. W원을 투자해서 i번 열차를 수리(개조)하면, 그 열차의 최대 속력을 Si + W * Vi 로 올릴 수 있다.
전체 M원을 투자해서 2호선의 속력을 향상 시킨다면, 2호선의 속력을 얼마까지 끌어 올릴 수 있을까? 단 한 열차에 투자되는 돈은 정수여야 하고, 당연히 투자되는 돈이 음수일 수는 없다.



입력 설명

전체 입력의 첫 번째 줄은 테스트 케이스의 개수를 나타내는 정수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 열차의 개수를 나타내는 정수 N과 투자할 돈을 나타내는 정수 M이 주어진다. 두 번째 줄에는 각 열차의 현재 최대 속력을 나타내는 정수 Si가 주어지고, 세 번째 줄에는 각 열차의 1원 당 속도 증가량을 나타내는 정수 Vi가 주어진다.



제약조건
  • T <= 100
  • 1 <= N <= 1,000
  • 1 <= M <= 109
  • 1 <= Si <= 106
  • 1 <= Vi <= 100


출력 설명

각 테스트 케이스에 대해, 가능한 2호선의 최대 속력을 한 줄에 출력한다.


입력 예시 Copy

3
5 3
1 2 3 4 5
3 2 1 2 3
6 10
1 3 5 2 4 6
6 4 2 5 3 1
4 20
1 5 3 5
6 3 3 2

출력 예시 Copy

4
7
18

출처/분류

LAVIDA