시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB102251948.718%

문제

현생을 살아가는 고양이 아리는 너무 바쁘고, 주어진 일을 모두 끝내야 한다는 압박감에 스트레스를 받고 있다.

아리는 이번 주까지 주어진 N개의 일을 모두 끝내야만 한다. N개의 일에 대해 i번(1 ≤ iN) 일에는 RiSi 가 존재한다. Ri는 아리가 이 일을 완전히 끝내기 위해서 i번 일을 반복해야 하는 횟수를 의미하며, Si 는 스트레스 수치를 의미한다. 아리는 한 가지 일을 시작했으면 시작한 일의 반복횟수만큼 모두 수행해야만 다음 일을 시작할 수 있으며, N개의 일을 수행하는 순서는 아리가 정할 수 있다.

아리는 지루한 것을 싫어하기 때문에 동일한 일을 반복하게 되면 받는 스트레스 수치가 커진다. 그리고 아리가 일을 여러 번 수행할 경우 피로누적으로 여기에 스트레스가 더 가중된다. 이에 따라 아리가 i번 일을 한 번 수행할 때 받는 스트레스 수치를 다음과 같은 식으로 나타낼 수 있다.

Si × (i번 일을 반복한 횟수) × (1 + (이전에 수행한 모든 일의 반복횟수의 총합) × 0.1)

아리는 N개의 일을 수행할 때, 아리가 수행한 모든 일에 대한 스트레스 수치의 총합이 최소가 되도록 모든 일의 순서를 정하려고 한다. 바쁜 아리를 대신해 N개의 일을 모두 수행했을 때 아리가 받을 스트레스 수치의 총합의 최솟값을 구해주자.

입력

첫째 줄에 아리가 이번 주 내로 수행해야 하는 일의 수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄부터 N개의 줄에 대해 i번째 줄에는 (i - 1)번 일의 반복 횟수 Ri-1와 (i - 1)번 일의 스트레스 수치 Si-1가 주어진다.

반복 횟수 R는 100보다 작거나 같은 양의 정수이고, 스트레스 수치 S는 10보다 크거나 같고 10,000 보다 작거나 같은 양의 정수 중 10의 배수이다.

출력

첫 번째 줄에 N개의 일을 모두 수행했을 때, 아리가 받을 스트레스 수치의 최솟값을 출력한다.

예제 입력 1

3
1 50
3 10
2 20

예제 출력 1

206

첫 번째로 1번 일을 1번 반복한다. 1번 일을 1번 수행할 때 아리가 받을 스트레스 수치는 50이다.

두 번째로 3번 일을 2번 반복한다. 3번 일을 2번 수행할 때 아리가 받을 스트레스 수치는 22 + 48로 70이다.

세 번째로 2번 일을 3번 반복한다. 2번 일을 3번 수행할 때 아리가 받을 스트레스 수치는 13 + 28 + 45로 86이다.

세 가지 일을 1번, 3번, 2번 순으로 수행했을 때 아리가 받는 스트레스 수치 합이 206이며, 이 값이 최솟값이다.