Evdən çıxma planı
Şəhərdə nüvə müharibəsi zamanı işçilərin təxliyəsi üçün xüsusi olaraq tikilmiş bələdiyyə binaları və sığınacaqlar mövcuddur. Hər bir sığınacağın müəyyən sayda insanı qəbul edə biləcək tutumu var. İdeal olaraq, hər bir bələdiyyə binasından bütün işçilər ən yaxın sığınacağa qaçmalıdır. Lakin bu zaman bəzi sığınacaqlar dolub-daşa bilər, digərləri isə yarıboş qala bilər.
Bu problemi həll etmək üçün Şəhər Şurası xüsusi bir təxliyə planı hazırlayıb. Onlar hər bir bələdiyyə binası üçün hansı sığınacağa neçə işçinin qaçmalı olduğunu müəyyən ediblər, fərdi bölgü məsələsini isə bələdiyyə binalarının daxili idarəçiliyinə həvalə ediblər.
Təxliyə planı hər bir binadakı işçilərin sayını nəzərə alır — hər bir işçi planda nəzərə alınmalıdır və hər bir sığınacağa göndərilən işçilərin sayı sığınacağın tutumunu aşmamalıdır.
Şəhər Şurası bəyan edir ki, onların təxliyə planı optimaldır, yəni şəhərin bütün işçilərinin təxliyə olunma müddəti minimumdur.
Şəhər meri, Şəhər Şurası ilə daimi qarşıdurmada olan biri olaraq, bu bəyanata çox da inanmır. Buna görə də o, təxliyə planını yoxlamaq üçün sizi müstəqil ekspert kimi işə götürüb. Sizin vəzifəniz ya Şəhər Şurasının planının optimal olduğuna əmin olmaq, ya da əksini sübut edərək bütün işçilərin təxliyə müddətini azaldan başqa bir təxliyə planı təqdim etməkdir.
Şəhərin xəritəsi kvadrat şəbəkə şəklində təqdim edilə bilər. Bələdiyyə binalarının və sığınacaqların yerləşməsi tam ədədlərlə verilir və (X_i, Y_i) koordinatlarında olan bələdiyyə binasından (P_j, Q_j) koordinatlarında olan sığınacağa təxliyə müddəti Dij = |X_i-P_j| + |Yi-Q_j| + 1 dəqiqə təşkil edir.
Giriş verilənləri
Giriş faylı şəhərin xəritəsinin və Şəhər Şurası tərəfindən təklif olunan təxliyə planının təsvirini ehtiva edir. Giriş faylının ilk sətiri boşluqla ayrılmış iki tam ədəd N (1 ≤ N ≤ 100) və M (1 ≤ M ≤ 100) ehtiva edir. N — şəhərdəki bələdiyyə binalarının sayı (hamısı 1 ilə N arasında nömrələnmişdir), M — sığınacaqların sayı (hamısı 1 ilə M arasında nömrələnmişdir).
Növbəti N sətir bələdiyyə binalarının təsvirini ehtiva edir. Hər bir sətir boşluqla ayrılmış tam ədədlər X_i, Y_i və B_i ehtiva edir, burada X_i, Y_i (-1000 ≤ X_i, Y_i ≤ 1000) — binaların koordinatları, B_i (1 ≤ B_i ≤ 1000) — binadakı işçilərin sayıdır.
Sığınacaqların təsviri növbəti M sətirdə verilir. Hər bir sətir boşluqla ayrılmış tam ədədlər P_j, Q_j və C_j ehtiva edir, burada P_j, Q_j (-1000 ≤ P_j, Q_j ≤ 1000) — sığınacağın koordinatları, C_j (1 ≤ C_j ≤ 1000) — sığınacağın tutumudur.
Növbəti N sətir təxliyə planının təsvirini ehtiva edir. Hər bir sətir ayrı bir binanın təxliyə planını təsvir edir. i-ci binadan təxliyə planı boşluqla ayrılmış M tam ədəd E_ij ehtiva edir. E_ij (0 ≤ E_ij ≤ 10000) — i-ci binadan j-ci sığınacağa təxliyə olunmalı işçilərin sayıdır.
Giriş faylında verilən planın düzgün olduğu təmin edilir.
Çıxış verilənləri
Əgər Şəhər Şurasının təxliyə planı optimaldırsa, bir söz OPTIMAL yazın. Əks halda, ilk sətirdə SUBOPTIMAL sözünü yazın və növbəti N sətirdə təxliyə planınızı (daha optimal olan) giriş faylındakı formatda yazın. Sizin planınız optimal olmaq məcburiyyətində deyil, lakin Şəhər Şurasının planından daha yaxşı olmalıdır.