소들의 다이어트는 농부 창호에게 다량의 건초를 남겨버리게 하였고,

창호는 경매를 열어 이를 팔아서 자신의 재고를 줄이고자한다.

그는 N(1≤N≤20,000)개의 서로 다른 건초 더미를 가지고 있으며; M(1≤M≤20,000)명의 농부가 경매에 참여한다.

i번째 농부 각각은 농부 창호에게 건초 더미를 사기 위해 지불하고자 하는 경매금액 Pi(1≤Pi≤1,000,000)을 입찰한다.

각 농부들은 하나의 건초더미를 사기를 희망한다.

입찰 금액을 보고 창호는 건초더미의 가격을 정해서 입찰금액보다 같거나 높을 경우

건초 더미의 가격 그대로 해당 농부에게 팔고자 한다.

이 경우 창호가 얻을 수 있는 이득은 (판 건초더미의 수) * (창호가 정한 건초더미의 가격)이다.

팔리지 않은 건초더미의 경우는 손해라고 가정하지 않는다.

가격을 정할 때 창호의 이득이 최대가 되도록 하는 프로그램을 작성하라.

만약에 이득이 동일 할 경우 창호가 정한 금액이 최대한 작게끔 하는 프로그램을 작성하라.

경매 timer 1s memory 128MB

경매 1s 128MB