Задача по информатике, помогите решить

Для определения местоположения объекта на Земном шаре используются географические координаты: широта (от -90° до 90°) и долгота (-180° до 180°). На гео­гра­фических кар­тах для оп­ре­де­ле­ния ко­ор­ди­нат объ­ек­тов ис­поль­зу­ют сет­ку ме­ри­диа­нов и па­рал­ле­лей. На глобусе параллель рисуется в виде окружности, все точки которой равноудалены от экватора. Все точки одной параллели имеют одинаковую широту, но различную долготу. Длины параллелей различны: они увеличиваются при приближении к экватору и уменьшаются — к полюсам. Экватор — самая длинная параллель. Каждый меридиан пересекается со всеми остальными в двух точках на северном и южном полюсе. Длины всех меридианов на глобусе равны 20 003,93 км. Все точки одного меридиана имеют одинаковую долготу, но разную широту. В международной практике за начальный меридиан (нулевой) принят Гринвичский, проходящий через Гринвич — административный округ Лондона.

Будем считать, что все города на Земле имеют целочисленные координаты: долготу от -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
57 -15 70
42 -110 80
-12 171 10
75 -82 500
-32 23 50
44 -54 50
380
Замечания
Пояснение к примеру. Проведём границы по меридианам -90°, -70° и 23°. При таком разделении в территорию между меридианами -90° и -70° попадет только город с координатами (75°, -82°), его население составляет 500 человек. В страну между меридианами -70° и 23° попадут города с координатами (57°, -15°), (44°, -54°), их общая численность составляет 70+50 = 120 человек. В страну между меридианами 23° и -90° попадут города с координатами (42°, -110°), (-12°, 171°), (-32°, 23°), их общая численность составляет 80 + 10 + 50 = 140 человек. При этом разность численности между наиболее населенной и наименее населенной страной равна 500 - 120 = 380 человек. Можно показать, что меньшей разности в данном случае добиться невозможно.
Система оценки и описание подзадач
Задача проверяется на 10 тестах по 10 баллов. За каждый тест баллы начисляются независимо. Максимальная оценка за задачу 100 баллов.