문제1202--DH 슈퍼마켓

1202: DH 슈퍼마켓

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 109  통과: 38
<<--이전 문제 소스 제출 다음 문제-->>

문제 설명  

DH씨는 컴퓨터 부품 관련 중고 물품만을 취급하는 상점을 운영하고 있다. 중고 물품의 특성상 매입하는 경로가 다양하며, 그에 따라 매입가격 또한 천차만별이다. 이러한 상황에서 DH씨는 각 물품별 적정가격을 결정하는 데 어려움을 겪고 있다. 왜냐하면, 비싼 가격으로 판매를 할 경우 물품을 구입하려는 고객들로부터 외면을 받을 것이고, 너무 싼 가격으로 판매를 할 경우 오히려 손해를 보게될 수 있기 때문이다.

이러한 상황에서 DH씨의 부인인 MS씨가 물품의 적정가격을 결정하기 위한 방법을 아래와 같이 제안하였다.

1) 동일한 종류의 물품들은 모두 같은 가격(new price)으로 판매하며, 이 가격(new price)으로 모두 판매했을 때 적어도 손해는 없어야 한다.
2) 1번의 조건을 만족하는 한에서 가장 적은 금액을 적정가격으로 결정한다.

MS씨가 제안한 내용을 바탕으로 적정가격을 계산하는 프로그램을 작성하시오.

입력 설명

첫 번째 줄에는 물품 종류의 개수 t을 입력한다. (단, 1 ≤ t ≤ 100)
두 번째 줄부터 물품 종류별로 물품의 개수 n, 각 물품별 매입가격 p를 두 줄에 걸쳐 입력한다.
(단, 1 ≤ n ≤ 100 이며, 1 ≤ p ≤ 1000001016 이다.)

출력 설명

각 물품 종류별로 적정가격을 출력하되, 각 물품 종류별로 줄바꿈을 하여 출력한다.

입력 예시 Copy

3
3
2 3 5
2
5 3
5
5 3 6 2 3

출력 예시 Copy

4
4
4

출처/분류

 ADH