가스 충전소

은하는 열심히 일한 덕분에 드디어 새 차를 뽑았습니다. 시운전으로 일직선 도로를 따라 차를 타고 목적지까지 이동하려고 합니다. 목적지까지 거리가 꽤 멀어서, 중간중간 주유소에서 연료를 넣으려고 합니다. 시운전 중에는 다음 조건을 지켜야 합니다.

• $i$번째 주유소는 길의 원점으로부터 오른쪽으로 $x_i$킬로미터 떨어진 위치에 있습니다. 이 주유소에서 넣을 수 있는 연료의 리터당 단가는 $p_i$이고, 총 $a_i$리터가 있습니다.
• 주유소에서는 $a_i$리터 이하의 범위에서 원하는 만큼 주유할 수 있습니다.
• 각 주유소에서 주유한 뒤 차에 들어 있는 연료의 양이 차의 연료 용량 $F$리터를 넘어서는 안 됩니다.
• 차는 1리터의 연료로 1킬로미터를 움직일 수 있습니다.
• 새 차는 시운전 전에 연료가 없습니다. 따라서 차의 시작 지점은 첫 번째 주유소입니다.
• 목적지는 길의 원점으로부터 오른쪽으로 $X$킬로미터 떨어진 위치입니다.

은하는 번 돈을 연료에 쓰는 것이 아까워서, 목적지까지 최소 비용으로 이동하려고 합니다. 여러분이 은하를 도와주어야 합니다.

첫 줄에 주유소의 개수 $N$, 목표 지점 $X$, 차의 연료 용량 $F$가 공백으로 구분되어 주어집니다. ($1 \leq N \leq 500\,000$; $1 \leq X, F \leq 10^9$)

둘째 줄부터 $N$개의 줄에 주유소 정보가 주어집니다. 모든 $1 \leq i \leq N$에 대해, $(i+1)$번째 줄에는 $x_i$, $p_i$, $a_i$가 공백으로 구분되어 주어집니다. ($0 \leq x_i < X$; $1 \leq p_i \leq 10^9$; $1 \leq a_i \leq F$) 같은 위치에 있는 주유소는 없으며, 주유소의 위치 $x_i$는 오름차순으로 주어집니다. 즉, 모든 $2 \leq i \leq N$에 대해 $x_{i-1} < x_i$입니다.

어떤 경로로 시운전을 진행해도 목적지에 도달할 수 없으면 첫째 줄에 -1을 출력합니다. 그렇지 않으면 첫째 줄에 시운전을 마치는 데 드는 최소 비용을 출력합니다.