Telefon#11202
Fermer Conun -dən -ə qədər nömrələnmiş və bir xətdə düzülmüş inəyi var. -ci inəyin cins identifikatoru b_i-dir və -dən -yə qədər diapazonda yerləşir. İnəklərin -ci inəkdən -ci inəyə mesaj ötürülməsinin optimal yolunu təyin etməkdə köməyinizə ehtiyacı var.
-ci inəkdən -ci inəyə mesaj ötürmək üçün |i - j| vahid vaxt tələb olunur. Lakin bütün cinslər bir-biri ilə mesaj mübadiləsi etməyə hazır deyillər. Cinslər arasında mesaj ötürmə imkanı k \times k ölçülü matrisi ilə verilir, burada S_{ij} = 1, əgər cinsindən olan inək cinsindən olan inəyə mesaj ötürməyə hazırdırsa, əks halda S_{ij} = 0-dır. Bununla belə, S_{ij} = S_{ji} olması vacib deyil, hətta S_{ii} = 0 ola bilər, əgər cinsindən olan inəklər bir-biri ilə mesaj mübadiləsi etməyə hazır deyillərsə.
-ci inəkdən -ci inəyə mesaj ötürmək üçün lazım olan minimum vaxt miqdarını təyin edin.
Birinci sətirdə iki tam ədəd verilir: n~(1 \le n \le 5 \cdot 10^4) və k~(1 \le k \le 50).
İkinci sətirdə tam ədəd b_1, b_2, \ldots, b_n verilir, burada 1 \le b_i \le k.
Sonrakı sətir matrisini təsvir edir. Hər sətir bitdən ibarət sətir olur, burada S_{ij} — -ci sətirin -ci bitidir.
Bir tam ədəd çap edin — -ci inəkdən -ci inəyə mesaj ötürmək üçün lazım olan minimum vaxt miqdarı. Əgər -ci inəkdən -ci inəyə mesaj ötürmək mümkün deyilsə, çap edin.
Optimal ötürmə ardıcıllığı belədir: 1 \to 4 \to 3 \to 5. Ümumi ötürmə vaxtı |1 - 4| + |4 - 3| + |3 - 5| = 6 təşkil edir.
Nümunə 1