가스 충전소

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

• $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을 출력합니다. 그렇지 않으면 첫째 줄에 시운전을 마치는 데 드는 최소 비용을 출력합니다.