#2143 고층빌딩 건설하기

26  1 s   128 MB  

Description

어떤 건설사가 부도가 나서 공사가 중단된 상태에 있는 고층빌딩이 있다. 이 빌딩에는 여러 개의 기둥이 있는데 전체 빌딩의 최종 높이는 이 기둥들 중에 가장 낮은 기둥의 높이와 같아지도록 설계되어 있다. 현재 짓다 만 빌딩에는 P개의 기둥이 있다. 그러나 각 기둥들은 굵기와 위치에 따라 기둥을 높이기 위한 비용이 모두 다르다.

만약 각 기둥의 현재 높이(Bi)와 100 달러를 투입할 경우 증가시킬 수 있는 높이(Hi)가 주어진다고 하자. 만약 D 달러를 투입해서 i번째 기둥을 높이면 그 기둥의 최대 높이는 Bi+Hi x (D / 100)로 높일 수 있다. 전체 W 달러를 투입해서 각 기둥들을 높일 경우 전체 빌딩의 최종 높이를 최고 얼마까지 높일 수 있겠는가?

Input

첫 줄에는 테스트 케이스의 수 T(1 <= T <= 10)가 입력된다. 각 테스트 케이스의 첫 번째 줄에는 기둥의 수를 나타내는 정수 P(1 <= P <= 50), 투입할 돈을 나타내는 정수 W(100 <= W <= 1000000, W는 100의 배수), 두 번째 줄에는 각 기중의 현재 높이를 나타내는 Bi(1 <= Bi <= 40)가 주어지고, 세 번째 줄에는 각 기둥에 100 달러를 투입할 경우 높일 수 있는 높이를 나타내는 정수 Hi(1<= Hi <= 10)가 주어진다.

Output

각 테스트 케이스에 대해 가능한 빌딩의 최종 높이를 한 줄에 하나씩 출력한다.

Sample Input

Sample Output

2
3 10000
5 8 10
5 2 3
6 300000
3 5 2 4 1 7
2 1 4 1 3 1
104
739

Source

동의대학교 멀티미디공학과 우영운(2014년 5월 15일)