E. Тенцинг и треугольник
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На двумерной плоскости имеется $$$n$$$ попарно различных точек и прямая $$$x+y=k$$$. Точка $$$i$$$ находится в точке $$$(x_i,y_i)$$$. Все точки имеют неотрицательные координаты и находятся строго под прямой. Другими словами, $$$0 \leq x_i,y_i, x_i+y_i < k$$$.

Тенцинг хочет стереть все точки. Он может выполнить следующие две операции:

  1. Нарисовать треугольник: Тенцинг выберет два неотрицательных целых числа $$$a$$$, $$$b$$$, которые удовлетворяют условию $$$a+b<k$$$, тогда все точки внутри треугольника, образованного прямыми $$$x=a$$$, $$$y=b$$$ и $$$x+y=k$$$ будут стерты. Можно показать, что этот треугольник является равнобедренным прямоугольным треугольником. Пусть длины сторон треугольника равны $$$l$$$, $$$l$$$ и $$$\sqrt 2 l$$$ соответственно. Тогда стоимость этой операции равна $$$l \cdot A$$$.

    Синяя область следующего рисунка описывает треугольник с $$$a=1,b=1$$$ со стоимостью $$$=1\cdot A$$$.

  2. Стереть определенную точку: Тенцинг выбирает целое число $$$i$$$, которое удовлетворяет условию $$$1 \leq i \leq n$$$ и стирает точку $$$i$$$. Стоимость этой операции равна $$$c_i$$$.

Помогите Тенцингу найти минимальную стоимость стирания всех точек.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$k$$$ и $$$A$$$ ($$$1\leq n,k\leq 2\cdot 10^5$$$, $$$1\leq A\leq 10^4$$$) — количество точек, коэффициент, описывающий гипотенузу треугольника и коэффициент, описывающий стоимость построения треугольника.

В следующих $$$n$$$ строках входных данных $$$i$$$-я строка содержит три целых числа $$$x_i,y_i,c_i$$$ ($$$0\leq x_i,y_i,x_i+y_i< k$$$, $$$1\leq c_i\leq 10^4$$$) — координаты $$$i$$$-й точки и стоимость ее стирания с помощью второй операции. Гарантируется, что координаты попарно различны.

Выходные данные

Выведите одно целое число –минимальную стоимость стирания всех точек.

Примеры
Входные данные
4 6 1
1 2 1
2 1 1
1 1 1
3 2 6
Выходные данные
4
Входные данные
6 7 1
4 2 1
3 3 1
5 1 4
3 2 5
4 1 1
0 6 4
Выходные данные
4
Входные данные
10 4 100
0 0 1
0 1 1
0 2 50
0 3 200
1 0 1
1 1 1
1 2 1
2 0 200
2 1 200
3 0 200
Выходные данные
355
Примечание

Рисунок первого примера:

Тенцинг выполняет следующие операции:

  1. построить треугольник с $$$a=3,b=2$$$, стоимость $$$=1\cdot A=1$$$.
  2. стереть первую точку, стоимость $$$=1$$$.
  3. стереть вторую точку, стоимость $$$=1$$$.
  4. стереть третью точку, стоимость $$$=1$$$.

Рисунок для второго примера: