성벽 보수

미레크는 문화재 보수 기술자다. 오늘 맡은 일은 낡은 요새의 성벽을 고치는 것이다. 성벽이 곧 무너질 참이라 서둘러야 한다. 그는 이런 성벽을 아주 빠르게 보수하는 로봇을 찾아내 사들였지만, 비용이 가장 적게 드는 보수 계획을 세우는 데서 막혔다.

성벽은 직선 하나로 생각한다. 보수가 필요한 지점의 좌표는 모두 적어 두었다. $i$번째 지점을 곧바로 보수하면 비용이 $C_i$이고, 보수를 미룰수록 비용이 얼마나 빨리 늘어나는지는 계수 $D_i$가 나타낸다. 시간 $t$가 지난 뒤에 $i$번째 지점을 보수하면 비용은 다음과 같다.

$C_i + t \cdot D_i$

로봇이 좌표 $x_1$에서 좌표 $x_2$로 이동하는 데 걸리는 시간은 $|x_1 - x_2|$이고, 한 지점을 보수하는 데 걸리는 시간은 0이다. 시간은 로봇이 처음 위치를 출발하는 순간부터 잰다. 망가진 지점을 모두 보수하는 비용의 최솟값을 구하라.

첫째 줄에 보수할 지점의 개수 $N$과 로봇의 처음 위치 $P$가 주어진다. ($1 \le N \le 2000$, $0 \le P \le 10^9$)

다음 $N$개 줄에 각 지점의 정보가 주어진다. $i$번째 줄에는 세 정수 $X_i$, $C_i$, $D_i$가 주어지고, 차례로 지점의 좌표와 두 비용 계수를 뜻한다. ($0 \le X_i \le 10^9$, $0 \le C_i, D_i \le 10^6$, $X_i \ne P$)

좌표가 같은 지점은 없다.

성벽의 모든 지점을 보수하는 최소 비용 $C$를 한 줄에 출력한다. 이 값은 32비트 정수 범위를 넘을 수 있다.

첫 번째 예제의 최적 계획은 다음과 같다.

• 로봇을 좌표 7에서 좌표 10으로 옮겨 시간 3에 첫 번째 지점을 보수한다.
• 로봇을 좌표 10에서 좌표 14로 옮겨 시간 $3 + 4 = 7$에 세 번째 지점을 보수한다.
• 로봇을 좌표 14에서 좌표 3으로 옮겨 시간 $3 + 4 + 11 = 18$에 두 번째 지점을 보수한다.

전체 비용은 $(32 + 3 \cdot 1) + (5 + 18 \cdot 1) + (0 + 7 \cdot 2) = 72$이다.