롤러코스터 선로

안나는 놀이공원에서 일하며 새 롤러코스터의 선로 건설을 맡고 있다. 그녀는 열차의 속도에 영향을 주는 특수 구간 $n$개를 이미 설계해 두었다. 구간에는 0부터 $n - 1$까지 번호가 매겨져 있다. 이제 이 구간들을 이어 붙여 롤러코스터의 최종 설계안을 제시해야 한다. 이 문제에서 열차의 길이는 0으로 본다.

각 $i$ ($0 \le i \le n - 1$)에 대해 특수 구간 $i$는 두 가지 속성을 가진다.

1. 구간에 진입할 때 속도 제한이 있다. 열차의 속도는 $s_i$ km/h 이하여야 한다.
2. 구간을 벗어날 때 열차의 속도는 진입 속도와 관계없이 정확히 $t_i$ km/h이다.

완성된 롤러코스터는 $n$개의 특수 구간을 어떤 순서로든 포함하는 하나의 선로다. 각 구간은 정확히 한 번씩 사용해야 한다. 연속된 구간은 선로로 연결한다. 안나는 구간의 순서를 정한 뒤 선로의 길이를 정한다. 선로 길이는 미터 단위이며 0을 포함한 음이 아닌 정수 아무 값이나 될 수 있다. 두 특수 구간 사이의 선로는 1미터마다 열차를 1 km/h씩 감속시킨다. 승차를 시작하면 열차는 1 km/h의 속도로 정해진 순서의 첫 번째 특수 구간에 진입한다.

최종 설계는 다음 조건을 만족해야 한다.

• 특수 구간에 진입할 때 어떤 속도 제한도 어기지 않는다.
• 열차의 속도는 어느 순간에도 양수다.

서브태스크 3을 제외한 모든 서브태스크에서는 구간 사이 선로 길이의 합이 최소가 되는 값을 구한다. 서브태스크 3에서는 모든 선로의 길이가 0인 유효한 설계가 존재하는지만 판단한다.

모든 서브태스크에서 $1 \le s_i \le 10^9$이고 $1 \le t_i \le 10^9$이다.