MIPT: 사람들을 잇다

모스크바 MIPT 캠퍼스는 현재 리모델링 중이다. 새로 지은 고층 주거단지에 신입생 기숙사가 들어선다. 한 줄로 늘어선 고층 건물이 $n$개 있고, 앞에서부터 $i$번째 건물의 층수는 $h_i$이다. 건물의 기초는 모두 같은 높이에 있고 층의 높이도 모두 같으므로, 어느 두 건물에서든 아래에서부터 같은 번호의 층은 같은 높이에 있다.

건물의 모든 층에는 주민이 정확히 한 명씩 살고 있다. 주민은 각 건물 안에서 엘리베이터로 위아래로 이동할 수 있다. 건물 $i$에서 한 층을 이동하는 데는 $tv_i$초가 걸린다.

이 사업의 유일한 단점은 출입구를 지킬 예산이 없다는 점이다. 그래서 단지 밖으로 나가거나 단지 안으로 들어올 수 없다. 이를 보완하기 위해 건물들을 잇는 연결 통로를 추가로 짓는다. 각 통로는 완전히 수평이어야 하므로, 두 건물의 같은 번호 층을 잇는다. 통로는 양 끝 사이에 있는 어떤 건물과도 겹칠 수 없다. 정식으로 쓰면, 건물 $i$와 건물 $j$ 사이에 층 $x$로 통로를 놓는다면, $i < k < j$인 모든 $k$에 대해 $h_k < x$이어야 하고, $h_i \geq x$와 $h_j \geq x$도 성립해야 한다.

통로를 지나는 데는 거리와 관계없이 $th$초가 걸린다. 통로는 비싸서 $n-1$개까지만 지을 수 있다.

주민들의 만족도를 유지하려면 다음 조건을 지켜야 한다.

• 어느 건물의 어느 층에서든 엘리베이터와 통로를 이용해 다른 건물의 어느 층으로든 갈 수 있다.
• 모든 주민에게 $1$부터 $R = \sum_{i=1}^n h_i$까지 번호를 매긴다. 주민 $x$가 엘리베이터와 통로를 이용해 주민 $y$의 거처에 도착하는 데 필요한 최소 시간(초)을 $d(x, y)$라 하자. 이때 $\sum_{1 \leq x < y \leq R} d(x, y)$가 최대한 작아야 한다.

MIPT 기획위원회가 이 사업을 마칠 수 있도록 도와라.

첫 줄에는 건물 수 $n$과 수평 통로 하나를 지나는 데 걸리는 시간 $th$가 주어진다($1 \leq n \leq 60$, $1 \leq th \leq 10^6$).

이어지는 $n$개의 줄은 건물을 설명한다. $i$번째 줄에는 두 정수 $h_i$와 $tv_i$가 주어진다. $h_i$는 건물의 층수이자 주민 수이고, $tv_i$는 건물 $i$에서 수직으로 한 층을 이동하는 데 걸리는 시간(초)이다($1 \leq h_i \leq 3000$, $1 \leq tv_i \leq 10^6$).

$R = \sum_{i=1}^n h_i \leq 3000$이 보장된다.

$n-1$개의 통로를 짓는 모든 유효한 방법 중에서 $\sum_{1 \leq x < y \leq R} d(x, y)$의 최솟값을 정수 하나로 출력한다.

첫 번째 샘플에서는 통로가 없으므로, 답은 수직 거리의 합 그 자체다.

나머지 샘플의 최적 배치는 아래 그림과 같다.

      #           #        
      #           #        
      #-------#   #       #
      #   #   #   #   #   #
      #   #   #   #   #   #
      #   #---#   #   #   #
      #   #   #   #---#---#
# #   #   # #-#   #   #-# #
#-#   #   # # #   #   # # #
# #   #-# # # #   # #-# # #