공포의 면담실

면접 대비

시간 제한1초메모리 제한1024 MB

요약

면접을 한 번에 하나씩 진행할 때, 각 부서가 업무를 마치는 시간의 합이 최소가 되는 값을 구합니다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

한국정보기술진흥원의 직원들은 6개월에 한 번씩 전 직원이 사장님과 일대일 면담을 한다.

진흥원에는 $N$ 개의 부서가 있다. 부서에 소속된 모든 직원이 면담을 마쳐야 해당 부서가 퇴근할 수 있다. 면담은 한 번에 한 명씩만 진행된다.

모든 부서의 퇴근 시간의 합이 최소가 되는 값을 구하시오.

입력

첫 번째 줄에 부서의 수 $N$ ( $1 \le N \le 1000$ )이 주어진다. 두 번째 줄부터 $N$ 개의 줄에 걸쳐 부서별 직원의 수와 직원당 면담에 소요되는 시간이 공백으로 구분되어 주어진다. 모든 부서의 직원 수의 합은 $1\,000\,000$ 명 이하이며, 직원당 면담에 소요되는 시간은 $1$ 분 이상 $1\,000$ 분 이하의 정수이다.

출력

모든 부서의 퇴근하는 데 걸리는 시간의 합의 최솟값을 분 단위로 출력한다.

예제1

예제 1
입력
```
3
2 5 50
2 20 10
1 100
```
예상 출력
```
300
```