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