N 명의 공주들이 수직선 위에 있다.

공주들은 수직선 위의 한 곳에 모여 파티를 하려고 한다.

위치 x 에 있는 공주가 위치 k 의 파티장으로 이동하는 데에는 | x - k| 의 시간이 걸린다.

그런데, 공주들은 예쁜 모습으로 파티장에 가야 하므로, 출발하기 전에 집에서 시간을 들여 화장을 해야 한다.

공주들마다 화장하는 시간이 각각 다르고, 이는 정수 t_i~~ ( 1 ≤ i ≤ N ) 로 주어진다.

즉, i 번째 공주의 위치를 x_i 라고 하면,

이 공주는 위치 k 의 파티장에 t_i + | x_i - k | 시간 후에 도착한다.

즉, 모든 공주는 시간 0 에 화장을 하기 시작하고, 화장이 끝나는 즉시 파티장으로 출발한다.

모든 공주가 파티장에 도착하면, 그 즉시 파티는 시작된다.

당신은 파티가 가장 빨리 시작하기를 원한다.

각 공주 별로 x_i,~~ t_i 가 주어졌을 때, 가장 빠르게 파티가 시작하기 위한 파티장의 위치를 구하자.

공주 파티 timer 2s memory 256MB

공주 파티 2s 256MB