반올림

문제 정보

문제

성진이는 얼마 전 "전대프연 행성"이라는 회사의 재무 담당자로 고용되었다.

이 회사에서는 특이한 방식으로 월급을 지급한다. 모든 직원의 회사 기여도를 %로 나타내어 구한 후, 한 달 월급 총액을 기여도에 곱하여 십만의 자리에서 반올림한 만큼 월급을 지급한다.

하지만 성진이는 똑똑했기 때문에, 입사하자마자 이 방식의 문제점을 금방 알아차릴 수 있었다.

예를 들어, 성진이가 35%, 승현이가 35%, 수찬이가 30%의 기여도를 가지고 있고, 총 월급이 200만원이라고 해 보자. 이 경우 성진이와 승현이는 200만원 \times 35% = 70만원, 수찬이는 200만원 \times 30% = 60만원이므로 셋 모두 100만원씩을 받게 된다. 하지만 예산은 총 200만원이므로, 300만원을 지급하게 되어 100만원의 예산 구멍이 생긴다!

깜짝 놀란 성진이는 각 직원의 기여도를 살짝 조정하여 예산을 맞추는 프로그램을 작성하려고 하였다. 이 회사의 월급 지급에는 몇 가지 규칙이 있는데,

(1) 미리 정한 총 월급 예산이 모자라지도, 남지도 않아야 한다.
(2) 기여도의 총합은 반드시 100%여야 하고, 모든 기여도는 항상 음이 아닌 정수여야 한다.
(3) 월급이 너무 많이 바뀌면 직원들이 혼란에 빠지기 때문에, 기여도 변화의 차이가 가장 큰 것을 최소화하여야 한다.

하지만 성진이는 매우매우 바빠서 그만 프로그램을 작성할 수 없게 되었다. 여러분이 성진이를 도와주어야 한다.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. (T \le 50)
각 테스트 케이스의 첫 번째 줄에는 직원의 수 N(1 \le N \le 1,000)과 총 월급액 M(1 \le M \le 100,000)이 공백을 사이에 두고 주어진다. M은 항상 100의 배수로 주어지며 단위는 만원이다.
각 테스트 케이스의 두 번째 줄에는 각 직원의 기여도를 나타내는 N개의 정수 A_i 가 공백을 사이에 두고 주어진다. (0 \le A_i \le 100, \sum{A_i} = 100, A_i의 단위는 퍼센트(%)이다)

출력

각 테스트 케이스마다 한 줄에 하나씩 가장 큰 기여도 변화의 최솟값을 퍼센트 단위로 출력한다.

예제 입력

3
3 200
35 35 30
3 300
35 35 30
3 100
49 2 49

예제 출력

6
0
1

노트

0개의 댓글이 있습니다.