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