Evdən çıxma planı#4586

Evdən çıxma planı

2 saniyə

64 meqabayt

Çox çətin

Şəhərdə bələdiyyə binaları və nüvə müharibəsi zamanı işçilərin təxliyəsi üçün xüsusi inşa olunmuş sığınacaqlar mövcuddur. Hər bir sığınacaqda yerləşə biləcək insanların sayı məhduddur. İdeal halda, hər bələdiyyə binasından olan bütün işçilər onlara ən yaxın sığınacağa getməli olardı. Lakin bu, bəzi sığınacaqların həddən artıq dolmasına, digərlərinin isə boş qalmasına səbəb ola bilər.

Bunu aradan qaldırmaq üçün Şəhər Şurası xüsusi bir təxliyə planı hazırlayıb. İşçilər ayrılıqda konkret sığınacağa təyin olunmaq əvəzinə, plan müəyyən edir ki, hər bələdiyyə binasından neçə işçi hansı sığınacağa getməlidir. Ayrı-ayrı əməkdaşların bölgüsü isə binaların daxili rəhbərliyinin öhdəsinə buraxılır.

Təxliyə planı hər binadakı işçilərin sayını nəzərə alır, beləliklə, hər bir işçi nəzərə alınır və heç bir sığınacaq öz tutumundan artıq dolmur.

Şəhər Şurası iddia edir ki, təklif etdikləri təxliyə planı optimallıq baxımından şəhərin bütün işçiləri üçün ümumi təxliyə müddətini minimuma endirir.

Şuranın bu iddiasına daim şübhə ilə yanaşan şəhər meri məsələni yoxlamaq üçün sizi müstəqil ekspert kimi cəlb edib. Sizin vəzifəniz - ya Şəhər Şurasının planının optimal olduğunu təsdiqləmək, ya da əksinə, daha qısa ümumi təxliyə müddəti olan alternativ plan təqdim etməklə sübut etməkdir.

Şəhər xəritəsi kvadrat tor kimi təsvir oluna bilər. Binaların və sığınacaqların yerləri tam ədədlərlə verilir. $X_{i}$ X_i, $Y_{i}$ Y_i koordinatlarında yerləşən binadan $P_{j}$ P_j, $Q_{j}$ Q_j koordinatlarına sahib sığınacağa getmək üçün tələb olunan təxliyə vaxtı belə hesablanır:

D_{ij} = ∣ X_{i} - P_{j} ∣ + ∣ Y_{i} - Q_{j} ∣ + 1

D_{ij} = |X_i - P_j| + |Y_i - Q_j| + 1

dəqiqə.

Giriş

Girişdə şəhər xəritəsi və Şəhər Şurasının təqdim etdiyi təxliyə planı təsvir olunur. Birinci sətirdə iki tam ədəd $N$ ( $1 \leq N \leq 100$ 1 \le N \le 100) və $M$ ( $1 \leq M \leq 100$ 1 \le M \le 100) verilir. $N$ — bələdiyyə binalarının sayı (1-dən $N$ -ə qədər nömrələnib), $M$ — sığınacaqların sayı (1-dən $M$ -ə qədər).

Sonrakı $N$ sətirin hər birində bir bələdiyyə binası təsvir olunur. Hər sətirdə $X_{i}$ X_i, $Y_{i}$ Y_i və $B_{i}$ B_i ədədləri verilir ( $- 1000 \leq X_{i}, Y_{i} \leq 1000$ -1000 \le X_i, Y_i \le 1000, $1 \leq B_{i} \leq 1000$ 1 \le B_i \le 1000) — $X_{i}$ X_i, $Y_{i}$ Y_i binanın koordinatları, $B_{i}$ B_i isə binadakı işçilərin sayıdır.

Növbəti $M$ sətir sığınacaqlar barədədir. Hər sətirdə $P_{j}$ P_j, $Q_{j}$ Q_j, $C_{j}$ C_j ədədləri verilir ( $- 1000 \leq P_{j}, Q_{j} \leq 1000$ -1000 \le P_j, Q_j \le 1000, $1 \leq C_{j} \leq 1000$ 1 \le C_j \le 1000) — $P_{j}$ P_j, $Q_{j}$ Q_j sığınacağın koordinatları, $C_{j}$ C_j isə onun tutumudur.

Daha sonra $N$ sətirin hər biri təxliyə planının bir sətrini təşkil edir: hər sətr $M$ ədəddən — $E_{ij}$ E_{ij} ( $0 \leq E_{ij} \leq 10000$ 0 \le E_{ij} \le 10000) ibarətdir: $E_{ij}$ E_{ij} $i$ -ci binadan $j$ -ci sığınacağa göndəriləcək işçilərin sayıdır.

Girişdə verilmiş planın düzgün olduğu zəmanətlidir.

Çıxış

Əgər Şəhər Şurasının təxliyə planı optimaldırsa, yalnız OPTIMAL sözünü çap edin.

Əks halda, birinci sətirdə SUBOPTIMAL sözünü, sonrakı $N$ sətirdə isə təkmilləşdirilmiş planınızı girişdəki formatda çap edin. Sizin təqdim etdiyiniz plan optimal olmalı deyil, sadəcə Şəhər Şurasının planından daha yaxşı olmalıdır.

Nümunələr

Nümunə 1