Забор в саду
Гари — внимательный садовник, владеющий прямоугольным участком, на котором растут деревья. На его земле произрастают два вида деревьев: сосны и лиственницы. Чтобы улучшить их жизнеспособность, он решил использовать специализированное удобрение для каждого вида деревьев вместо универсального, которое применял ранее.
Поскольку у Гари много деревьев, он не может удобрять каждое дерево по отдельности. Поэтому он решил построить забор, чтобы разделить участок на две части: на одной стороне использовать удобрение для сосен, а на другой — для лиственниц. Новый забор будет представлять собой прямую линию, соединяющую две различные точки на границе участка.
К сожалению, каждое удобрение идеально подходит только для своего вида деревьев, но губительно для другого. После установки забора и выбора удобрения для каждой стороны, лиственницы на стороне сосен и сосны на стороне лиственниц будут вырублены, чтобы избежать их гибели, которая испортит пейзаж. Более того, перед установкой забора необходимо вырубить деревья любого вида, находящиеся прямо на линии, где будет расположен забор.
Гари очень дорожит своими деревьями. В зависимости от вида, возраста и других факторов, каждое дерево имеет определенную ценность. Садовник хочет построить забор и выбрать удобрение для каждой стороны так, чтобы минимизировать свои потери, где потери — это сумма ценностей деревьев, которые будут вырублены.
Вас наняли для постройки забора. Прежде чем приступить к работе, сообщите Гари, сколько он потеряет при оптимальном выборе местоположения забора и удобрения для каждой стороны.
Входные данные
Каждый тестовый случай описывается несколькими строками. Первая строка содержит два целых числа P и L, обозначающих количество сосен и количество лиственниц соответственно (1 ≤ P, L ≤ 1000). Каждая из следующих P строк описывает сосну. Затем каждая из следующих L строк описывает лиственницу. Деревья представлены как точки на плоскости XY. Каждое дерево описывается тремя целыми числами X, Y и V, где X и Y — координаты дерева (-10^5 ≤ X, Y ≤ 10^5), а V — его ценность (1 ≤ V ≤ 1000). Можно предположить, что в каждом тестовом случае ни у каких двух деревьев нет одинакового местоположения.
Последний тестовый случай завершается строкой, содержащей два нуля.
Выходные данные
Для каждого тестового случая выведите строку с целым числом, представляющим минимально возможные потери для садовника.