D1. Суперколлайдер
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задача состоит из двух подзадач: за решение подзадачи D1 вы получите 3 балла, за решение подзадачи D2 вы получите 16 баллов.

Манао — главный архитектор плана постройки нового суперколлайдера. Его задача — выбрать место, на котором можно построить коллайдер максимального размера. В новом суперколлайдере должно происходить столкновение частиц, движущихся с равной скоростью из четырех направлений, поэтому коллайдер будет иметь четыре камеры ускорения равной длины. Также, чтобы минимизировать помехи от магнитного поля Земли, камеры должны быть либо параллельны, либо перпендикулярны магнитному полю планеты. Таким образом, Манао ищет место, на котором можно построить большую структуру в форме плюса.

Чтобы уложиться в бюджет, камеры ускорения должны быть выложены вдоль длинных ровных трактов на местности. Манао уже провел топографическое исследование, в результате которого были обнаружены все такие тракты, параллельные или перпендикулярные магнитному полю Земли. Для постройки максимально большого суперколлайдера, Манао должен определить, какие два тракта создают самую большую фигуру в форме плюса. Иными словами, он должен найти два перпендикулярных тракта, которые пересекаются и имеют наибольшую длину от центра созданного ими «плюса» до ближайшего конца одного из трактов.

Исследование, проведенное Манао, выявило немало трактов, как в направлении север-юг, так и в направлении запад-восток. Ему требуется ваша помощь, чтобы быстро определить место, где будет построен суперколлайдер.

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

Первая строка содержит пару разделенных единственным пробелом чисел n и m, где n — количество трактов в направлении север-юг, а m — количество трактов в направлении восток-запад.

Каждая из следующих n строк содержит три разделенных пробелом целых числа xi, yi, li, где (xi, yi) — самая северная точка i-го тракта в направлении север-юг, а li — это длина тракта. Таким образом, соответствующий тракт можно представить как вертикальный отрезок от (xi, yi) до (xi, yi + li).

Далее следует m строк, описывающих тракты в направлении запад-восток. Каждая из этих строк содержит три разделенных пробелом целых числа xi, yi, li, где (xi, yi) — это самая западная точка i-го тракта, а li — его длина. Таким образом, соответствующий тракт можно представить как горизонтальный отрезок от (xi, yi) до (xi + li, yi).

Значения всех xi и yi в диапазоне между -100000000 и 100000000, включительно. Значения всех li в диапазоне между 1 и 100000000, включительно. Никакая пара вертикальных отрезков не касается и не пересекается, и никакая пара горизонтальных отрезков не касается и не пересекается.

Задача состоит из двух подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже.

  • В подзадаче D1 (3 балла), n и m будут между 1 и 1000, включительно.
  • В подзадаче D2 (16 баллов), n и m будут между 1 и 50000, включительно.
Выходные данные

Выведите единственное целое число — максимальный возможный размер суперколлайдера, построенного на паре ортогональных трактов. Размер суперколлайдера определяется как длина одной из камер ускорения. Иными словами, размер суперколлайдера — это расстояние от пересечения двух трактов до ближайшего конца одного из трактов. Если никакая пара ортогональных трактов не пересекается, построить коллайдер невозможно и ответом должен быть 0.

Примеры
Входные данные
1 2
4 0 9
1 1 8
1 2 7
Выходные данные
2
Примечание

Рассмотрим пример. Есть вертикальный отрезок из (4, 0) в (4, 9) и два горизонтальных отрезка: между (1, 1) и (9, 1), и между (1, 2) и (8, 2). Наибольшая фигура в форме плюса получается из вертикального отрезка и второго из горизонтальных отрезков. Ее центр будет в точке (4, 2).

Ответом на тест является число 2, так как ближайший из концов этих двух отрезков находится в точке (4, 0), на расстоянии 2 от (4, 2). Коллайдер будет выложен вдоль отрезков (2, 2)-(6, 2) и (4, 0)-(4, 4).