공포의 면담실

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

요약

면담을 한 명씩 진행할 때 모든 부서의 퇴근 시간 합이 최소가 되는 순서를 정해 그 최솟값을 구한다.

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

문제

한국정보기술진흥원의 직원들은 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
```