На двумерной плоскости имеется \(n\) попарно различных точек и прямая \(x+y=k\). Точка \(i\) находится в точке \((x_i,y_i)\). Все точки имеют неотрицательные координаты и находятся строго под прямой. Другими словами, \(0 \leq x_i,y_i, x_i+y_i < k\).
Тенцинг хочет стереть все точки. Он может выполнить следующие две операции:
Синяя область следующего рисунка описывает треугольник с \(a=1,b=1\) со стоимостью \(=1\cdot A\).
Помогите Тенцингу найти минимальную стоимость стирания всех точек.
Первая строка содержит три целых числа \(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
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач