수행 시간
면접 대비시간 제한2초메모리 제한128 MB
계급별로 나뉜 n대의 컴퓨터가 아래 계급의 전달을 모두 받은 뒤 동작한다고 할 때 작업이 끝나는 시각을 구합니다.
문제
특정 임무를 수행하기 위해 n개의 컴퓨터로 이루어진 시스템이 있다고 하자. 이 시스템의 동작 체계는 아래와 같다.
- 모든 컴퓨터는 1번부터 n번까지 번호가 매겨져 있다. 모든 컴퓨터는 각자의 계급과 동작 속도를 가지고 있다. 또한 계급과 동작 속도는 모두 양의 정수이다.
- i번 컴퓨터와 j번 컴퓨터 간의 전송 시간은 (i - j)2이다.
- 각 n개의 컴퓨터의 계급은 c1, c2, … cn이다. (1 ≤ c1 ≤ c2 ≤ … ≤ cn ≤ n). 주어진 컴퓨터의 계급을 오름차순으로 정렬했을 경우, | cj -cj-1 |≤ 1이다.
- 제일 낮은 계급의 컴퓨터를 제외한 모든 컴퓨터들은 자신보다 한 단계 낮은 계급의 모든 컴퓨터에게 정보를 전달받아야만 동작을 시작 할 수 있다. 이 때, 동작을 시작하기 위해서는 그 컴퓨터의 동작 속도만큼의 시간이 소요된다.
- 제일 낮은 계급의 컴퓨터는 전달 받을 정보가 없다. 따라서 시스템 시동과 동시에 동작한다.
- 계급이 c인 컴퓨터가 동작을 마치면 c+1의 계급을 가진 모든 컴퓨터에 정보를 전달 후 종료된다.
- 모든 컴퓨터가 동작을 마치고 종료되면 이 시스템의 임무 수행이 끝난다.
- 가장 낮은 계급은 1이다.
이 시스템에 대한 정보가 주어졌을 때 임무 수행이 끝날 때까지 걸린 시간을 구하여라.
입력
첫 번째 줄에는 컴퓨터의 개수 n이 주어진다. (3 ≤ n ≤ 100) 두 번째 줄부터 n개의 줄에 걸쳐 1번부터 n번까지 각 컴퓨터의 계급과 동작 속도 t가 공백을 두고 주어진다. (1 ≤ t ≤ 100)
출력
문제의 정답을 출력하라.