Bağ Hasarı
"'markdown Gary diqqətli bir bağbandır və onun düzbucaqlı bir sahəsi ağaclarla doludur. Onun torpağında iki növ ağac var: şamlar və qovaqlar. Onların canlılığını artırmaq üçün o, indiyə qədər istifadə etdiyi ümumi gübrə əvəzinə, hər ağac növü üçün xüsusi gübrə istifadə etməyə qərar verdi.
Gary-nin çoxlu ağacı olduğu üçün gübrələri hər ağaca ayrı-ayrılıqda yerləşdirmək mümkün deyil. Bu səbəbdən o, sahəni iki yerə ayırmaq üçün bir çəpər tikməyə qərar verdi və bir tərəfdə şam gübrəsi, digər tərəfdə isə qovaq gübrəsi istifadə edəcək. Yeni çəpər, torpağın sərhədində yerləşən iki fərqli nöqtəni birləşdirən düz xətt üzərində tikiləcək.
Təəssüf ki, hər gübrə nəzərdə tutulduğu ağac növü üçün əladır, lakin digərinə ölümcül təsir göstərir. Çəpəri tikdikdən və hər tərəfdə hansı gübrənin istifadə olunacağını qərarlaşdırdıqdan sonra, şamların olduğu tərəfdəki qovaqlar və qovaqların olduğu tərəfdəki şamlar kəsiləcək, çünki bu, mənzərəni məhv edəcək yavaş bir ölümün qarşısını alacaq. Bundan əlavə, çəpəri tikməzdən əvvəl, çəpərin yerləşəcəyi xətt üzərində birbaşa yerləşən hər hansı bir növ ağac kəsilməlidir.
Əlbəttə ki, Gary ağaclarını sevir. Onların növü, yaşı və digər amillərə görə hər ağacın müəyyən bir dəyəri var. Bağban çəpəri elə tikmək və hər tərəfdə hansı gübrənin istifadə olunacağını elə seçmək istəyir ki, onun itkisi minimuma ensin, burada itki kəsiləcək ağacların dəyərlərinin cəmidir.
Siz çəpəri tikmək üçün işə götürüldünüz. İşinizə başlamazdan əvvəl, Gary-yə çəpərin yerini optimal seçərkən və hər tərəf üçün gübrəni seçərkən nə qədər itkiyə məruz qalacağını deyin.
Giriş verilənləri
Hər test halı bir neçə sətirdə təsvir olunur. İlk sətir müvafiq olaraq şamların və qovaqların sayını təmsil edən iki tam ədəd P və L ehtiva edir (1 ≤ P, L ≤ 1000). Növbəti P sətirin hər biri bir şamı təsvir edir. Bundan sonra, növbəti L sətirin hər biri bir qovağı təsvir edir. Ağaclar XY müstəvisində nöqtələr kimi modelləşdirilir. Hər ağac üç tam ədəd X, Y və V ilə təsvir olunur, burada X və Y ağacın koordinatlarıdır (-10^5 ≤ X, Y ≤ 10^5), və V onun dəyəridir (1 ≤ V ≤ 1000). Hər test halında heç bir iki ağacın eyni yerdə olmadığını qəbul edə bilərsiniz.
Son test halı iki sıfır ehtiva edən bir sətirlə tamamlanır.
Çıxış verilənləri
Hər test halı üçün bağban üçün mümkün olan minimum itkini təmsil edən bir tam ədəd ilə bir sətir çıxarın. "'