НА ПИТОНЕ!! Для определения местоположения объекта на Земном шаре используются географические координаты: широта (от -90° до 90°) и долгота (-180° до 180°).
Будем считать, что все города на Земле имеют целочисленные координаты: долготу от -180° до 179° и широту от -89° до 89° (будем считать, что на полюсах городов нет). Размером города будем пренебрегать, то есть будем считать, что город - это точка на Земле. И, конечно, в одной точке не может быть два разных города. В каждом городе живёт какое-то количество жителей.
Три правителя нашей планеты решили создать три страны, разделив между собой все города Земного шара. Границы своих владений они хотят проводить по меридианам, причем города, расположенные на граничном меридиане относятся к территории, расположенной правее этого меридиана, то есть в сторону увеличения долготы. Будем считать, что меридиан с долготой -180° правее меридиана с долготой 179°.
Для справедливости они хотят разделить все города так, чтобы количество жителей в наиболее населённой стране отличалось от количества жителей в наименее населённой стране минимально.
Исходные данные
В первой строке записано целое число n (1 ≤ n ≤ 64440) – количество городов на планете. Каждая из следующих n строк содержит описание i-го города в виде тройки чисел: широта X (-89 ≤ X ≤ 89), долгота Y (-180 ≤ Y ≤ 179), численность P (1 ≤ P ≤ 100000).
Результат
Выведите одно целое число - минимальную разность между наиболее населенной и наименее населенной страной, которой можно добиться, разделяя города указанным выше
Пример
исходные данные результат
6 380
57 -15 70
42 -110 80
-12 171 10
75 -82 500
-32 23 50
44 -54 50
