시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 128 MB 87 63 52 69.333%

문제

특정 임무를 수행하기 위해 n개의 컴퓨터로 이루어진 시스템이 있다고 하자. 이 시스템의 동작 체계는 아래와 같다.

  1. 모든 컴퓨터는 1번부터 n번까지 번호가 매겨져 있다. 모든 컴퓨터는 각자의 계급과 동작 속도를 가지고 있다. 또한 계급과 동작 속도는 모두 양의 정수이다.
  2. i번 컴퓨터와 j번 컴퓨터 간의 전송 시간은 (i - j)2이다.
  3. 각 n개의 컴퓨터의 계급은 c1, c2, … cn이다. (1 ≤ c1 ≤ c2 ≤ … ≤ cn ≤ n). 주어진 컴퓨터의 계급을 오름차순으로 정렬했을 경우, | cj -cj-1 |≤ 1이다. 
  4. 제일 낮은 계급의 컴퓨터를 제외한 모든 컴퓨터들은 자신보다 한 단계 낮은 계급의 모든 컴퓨터에게 정보를 전달받아야만 동작을 시작 할 수 있다. 이 때, 동작을 시작하기 위해서는 그 컴퓨터의 동작 속도만큼의 시간이 소요된다.
  5. 제일 낮은 계급의 컴퓨터는 전달 받을 정보가 없다. 따라서 시스템 시동과 동시에 동작한다.
  6. 계급이 c인 컴퓨터가 동작을 마치면 c+1의 계급을 가진 모든 컴퓨터에 정보를 전달 후 종료된다.
  7. 모든 컴퓨터가 동작을 마치고 종료되면 이 시스템의 임무 수행이 끝난다.
  8. 가장 낮은 계급은 1이다.

이 시스템에 대한 정보가 주어졌을 때 임무 수행이 끝날 때까지 걸린 시간을 구하여라.

입력

첫 번째 줄에는 컴퓨터의 개수 n이 주어진다. (3 ≤ n ≤ 100) 두 번째 줄부터 n개의 줄에 걸쳐 1번부터 n번까지 각 컴퓨터의 계급과 동작 속도 t가 공백을 두고 주어진다. (1 ≤ t ≤ 100)

출력

문제의 정답을 출력하라.

예제 입력 1

9
1 1
3 9
3 1
4 2
4 2
2 5
1 30
4 2
5 3

예제 출력 1

103

출처

University > 숭실대학교 > 2018 SCAL-MOOKJA E번

University > 중앙대학교 > 2018 SCAL-MOOKJA E번