물건 팔기
면접 대비시간 제한2초메모리 제한128 MB
구매자별 최대 지불 가능 금액과 배송비가 주어질 때, 이익을 내는 구매자들의 합을 최대화하는 판매 가격(동일하면 최소값)을 구합니다.
문제
판매자는 새 상품 하나를 가장 큰 이익으로 팔려고 한다. 구매 의사가 있는 사람은 N명이며, 각 사람 i에게는 지불할 수 있는 최대 금액 Ai와 그 사람에게 배송하는 데 드는 비용 Bi가 있다.
판매 가격을 P로 정하면 Ai가 P 이상인 사람만 구매할 수 있다. 판매자는 구매 가능한 사람 중에서도 손해가 나는 사람에게는 팔지 않아도 된다. 따라서 사람 i에게 팔 때 얻는 이익은 P - Bi이고, 이 값이 양수일 때만 판매한다고 볼 수 있다.
N명 각각의 Ai와 Bi가 주어질 때, 총이익을 최대로 만드는 판매 가격 P를 구하시오.
입력
첫째 줄에 구매할 의향이 있는 사람의 수 N이 주어진다. N은 50보다 작거나 같다.
둘째 줄부터 N개의 줄에 걸쳐 각 사람이 지불할 수 있는 최대 금액 Ai와 배송비 Bi가 공백으로 구분되어 주어진다. 두 값은 모두 10^6 이하인 음이 아닌 정수이며, 배송비는 0일 수도 있다.
출력
총이익을 최대로 만드는 가격을 출력한다. 최대 이익을 만드는 가격이 여러 개라면 그중 가장 낮은 가격을 출력한다.
어떤 가격으로도 양의 이익을 얻을 수 없다면 0을 출력한다.