문제1048--AP 배분

1048: AP 배분

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

한기대 기숙사에는 각 건물마다 AP 가 설치되어 있어 인터넷을 이용할 수 있다.
그런데 각 기숙사 건물마다 인터넷 속도가 너무 차이가 난다며 불만이 접수되어 원인을 파악해보니 속도가 느린 기숙사 건물의 경우 입주한 학생 대비 AP 수가 너무 적어 한 AP 에 많은 이용자들이 몰리면서 속도 저하가 발생하였다.

똑똑한 사감 송영준(04학번, 애묘가)은  각 기숙사 건물의 학생 수와 가용한 총 AP 개수를 조사하여 한 AP 에 접속하는 학생 수를 최소화할 수 있도록 AP를 재배치 하고자 한다. 단, 모든 건물에서 인터넷 이용이 가능해야 하므로 각 건물마다 적어도 1개의 AP 는 설치를 해야만 한다.

위의 조건을 만족하도록 AP를 설치하였을 때 한 AP 당 접속하는 학생 수의 최대 값은 얼마인지 출력하라.

입력 설명

첫 줄에는 테스트 케이스 T (1 <= T <= 100) 이 주어집니다.
다음 줄부터 각 줄에는 하나의 테스트 케이스에 대하여 기숙사 수 B와 AP의 개수 K 가 주어집니다.
그리고 이어서 B개의 줄에 각 기숙사의 학생수 B1, B2 ... Bn 이 주어집니다.

기숙사 수 B 는 1이상 100 이하이며, AP의 개수 K 는 항상 기숙사 수 B보다 크거나 같으며 1,000,000 이하입니다.
각 기숙사의 학생수는 1이상 1,000,000 이하 입니다.

출력 설명

한 줄에 하나씩 한 AP당 접속하는 학생 수를 최소화 하도록 AP를 배치하였을 때 AP당 학생 수의 최대 값을 출력합니다.

입력 예시 Copy

2
2 7
200
500
6 10
1
1
1
2
2
2

출력 예시 Copy

100
1