문제
농부 창호의 N(1≤N≤50,000)마리의 소들은 완전히 일렬로 서서 "음메"하며 울고 있다.
각각의 소들은 고유한 키 h를 가지는데 1..2,000,000,000 nano미터 (역주: 10의 -9승 단위 미터) 범위의 값을 가진다.
(농부 창호은 정확성에 있어서 상당히 까다로운 사람이다).
각각의 소들은 v의 소리 크기로 "음메" 우는데 1..10,000 범위의 값을 가진다.
이 "음메" 울기는 양쪽 방향으로 연속적으로 퍼지게 된다(물론 양 끝의 소들에겐 해당되지 않는다).
신기하게도, 그 소리는 각 방향의 가장 가까우면서 지금 "음메" 우는 소보다 키가 큰 소만 들을 수 있다
(그래서 "음메" 울기는 우는 소의 왼쪽과 오른쪽에 그 소보다 키가 큰 소들의 존재 여부에 따라 0, 1 혹은 2마리 다른 소에게만 들리게 된다).
주어진 소가 듣게되는 "음메" 울음소리의 전체적인 크기는 그 소에게 도달될 수 있는 다른 소들의 "음메" 울음소리 v의 총 합들과 같다.
몇몇 소들(아마도 키가 큰)은 매우 큰 소리를 듣게 될 것이기 때문에,
농부 창호은 가장 위협적인 크기의 소리를 듣게되는 소에게 귀마개를 사주려고 한다.
어떤 소가 듣게되는 가장 큰 울음 소리의 크기를 계산하라.
입력
첫 번째 줄에 단 1개의 정수 N입력두 번째 줄부터 N+1번째 줄의 i+1번째 줄은 공백으로 구분된 두 정수 h와 v(i번째 위치에 선 소의 정보) 를 포함한다.
출력
어떤 한 소가 듣게되는 가장 시끄러운 소리의 크기를 출력한다.
예제
3
4 2
3 5
6 10
7
힌트
로그인해야 코드를 작성할 수 있어요.