농구 토너먼트 timer 2s memory 512MB

농구 코치인 당신은 n명의 선수들을 관리하며, 각 선수들은 1번부터 n번까지 번호가 매겨져 있다. i번 선수의 키는 h_i cm이다.

다음은 P(S)에 관한 정의이다.

- f(i , j)=h_i+h_j이다.

- P(S)는 선수 팀(집합) S에 존재하는 모든 선수들의 번호를 가지고 만든 순서쌍 (i,j)에 있어서, f(i , j)의 합이다. 수식으로 표현하자면 아래와 같다.

- 예를 들어, 어떤 선수 팀 S에 속한 두 선수의 키가 {2, 3} 이라면, P(S) = f(1 , 1) + f(1 , 2) + f(2 , 1) + f(2 , 2) = 4+5+5+6 = 20이다.

정올 농구 토너먼트는 방식이 조금 특이하여, 이하 설명을 만족하는 팀만이 출전할 수 있다. 

토너먼트는 m라운드로 진행되며, 각 라운드마다 l, r, x가 주어진다. 

당신은 선수 번호가 구간 [l,r]에 있는 선수들 중, 연속된 번호를 가진 선수들로만 팀을 꾸릴 수 있다.

(예를 들어, l = 1이고 r = 3이면, 선수 1과 선수 3만으로 팀을 꾸릴 수는 없다.) 

이 팀을 집합 S라고 할 때, P(S)가 x 이상이어야만 한다는 규칙이 있다. 

당신은 이 규칙을 만족하면서 그 팀의 선수들의 가장 큰 키가 최소가 되도록 하고 싶다.

각 라운드마다 가장 큰 키를 최소화시키는 팀을 꾸릴 때, 그 최소값을 출력하는 프로그램을 작성하라.​