KOI나라에서 미술 전시회를 개최하기로 했다.

전시회는 나라 전체에서 모인 다양한 미술품이 전시될 예정이다.

전시되는 미술품의 후보로 N개가 선정되었다.

각각의 미술품에는 크기와 가치가 자연수로 책정되어 있다.

i번째 미술품의 크기는 A_i, 가치는 B_i이다(1 ≦ i ≦ N). 전시회에서는 이러한 미술품들 중에서 1개 이상을 선택해 전시한다.

전시회 회장은 충분히 넓기 때문에 N개의 미술품을 모두 전시 할 수 있다.

그러나 방문객의 미적 감각은 매우 까다롭기 때문에, 크기가 비슷한 미술품들만을 전시하고 싶다.

또한, 가능한 가치 있는 미술품을 많이 전시하고 싶다. 전시회 관리자는 이런 점을 고려해 다음 조건을 충족하도록 전시하는 미술품을 선택하기로 결정했다.

• 전시된 미술품 중 크기가 가장 큰 것의 크기를 A_max, 크기가 가장 작은 것의 크기를 A_min,

전시된 미술품들의 가치의 합을 S라고 할 때, S - (A max - A min)가 최대가 되게 미술품을 선택한다.

전시되는 미술품 후보의 개수와 각 미술품의 크기 및 가치가 주어졌을 때, S - (A_max – A_min) 의 최댓값을 구하여라.

전시회 timer 1초 memory 256MB

전시회 1초 256MB