존들의 소가 다이어트를 해 건초더미가 남는다.이를 팔기 위해 경매를 하기로 하였다.
팔려는 건초더미는 같은 양으로 N (1 <= N <= 1,000) 개이고 , 고객은 동네에 사는 M(1 <= M <= 1,000) 명의 농부이다.
농부 i 는 존에게 한 더미를 사기위해 지불할 Pi (1 <= P_i <= 1,000,000)를 제출한다. 모든 농부는 한 더미만 필요하다.
다른 농부들이 서로 질투하는 것을 방지하기 위해 모든 더미를 일정한 가격에 팔기로 하였다. 즉 이 가격 이상을 적은 농부는 살 수 있고 아니면 살 수 없다.
그가 벌어들일 수입을 최대화하기 위한 가장 낮은 가격을 찾아라.
입력 5 4 2 8 10 7 출력 7 21
입력 5 더미의 건초더미를 가지고 있고 4 명의 농부는 각각 2 , 8 , 10 , 7 을 지불할 용의가 있다. 출력 가격 7 을 정하면 3 명의 농부에게 팔 수 있고 그 때 21 을 벌 수 있다.
출처: usaco NOV 2008 bronze