Description
서울 지하철 2호선은 순환선이다. 순환선의 어떤 두 열차는 속력 차이가 많이 날 때, 열차 간 간격이 좁아져서 부딪힐 위험이 생긴다. 그래서 2호선의 모든 열차는 순환선을 돌고 있는 열차 중 가장 느린 열차에 속력을 맞출 수밖에 없고, 그게 결국 2호선의 속력이 된다.
2호선에는 N개의 열차가 있다. 모든 열차는 생산 연도도 다르고, 관리 상태도 다르기 때문에 낼 수 있는 최대 속력과 수리(혹은 개조) 비용이 각각 다르다. 각 열차의 현재 최대 속력 Si와 1원 당 속도 증가량 Vi가 주어진다. W원을 투자해서 i번 열차를 수리(개조)하면, 그 열차의 최대 속력을 Si + W * Vi 로 올릴 수 있다.
전체 M원을 투자해서 2호선의 속력을 향상 시킨다면, 2호선의 속력을 얼마까지 끌어 올릴 수 있을까? 단 한 열차에 투자되는 돈은 정수여야 하고, 당연히 투자되는 돈이 음수일 수는 없다.
Input
전체 입력의 첫 번째 줄은 테스트 케이스의 개수를 나타내는 정수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 열차의 개수를 나타내는 정수 N과 투자할 돈을 나타내는 정수 M이 주어진다. 두 번째 줄에는 각 열차의 현재 최대 속력을 나타내는 정수 Si가 주어지고, 세 번째 줄에는 각 열차의 1원 당 속도 증가량을 나타내는 정수 Vi가 주어진다.
제약조건
-
T <= 100
-
1 <= N <= 100
-
1 <= M <= 30,000
-
1 <= Si <= 100
-
1 <= Vi <= 100
Output
각 테스트 케이스에 대해, 가능한 2호선의 최대 속력을 한 줄에 출력한다.
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