Uçmaq ya uçmamaq
Mars'a xoş gəlmisiniz! İlk missiyanız K şəhərinə A_1, A_2, …, A_K ardıcıllıqla məktublar çatdırmaqdır. Mars N şəhərdən ibarətdir və bu şəhərlər müxtəlif uzunluqlu yollarla birləşdirilib. i-ci şəhərdə sürətinizi artırmaq üçün istifadə edə biləcəyiniz P_i sayda UFO var. Əgər yolun uzunluğu x olarsa, piyada gedərkən 5x dəqiqə sərf edəcəksiniz, lakin UFO ilə uçduğunuzda yalnız x dəqiqə sərf edəcəksiniz. Missiyanı minimal vaxtda tamamlamalısınız və hər bir UFO yalnız bir dəfə istifadə edilə bilər. UFO-dan istifadə edərkən məktubları çatdıra bilməzsiniz, buna görə məktub göndərmək üçün UFO-dan enməlisiniz.
Giriş verilənləri
Bir neçə test halı mövcuddur və bunlar EOF ilə bitir. Hər test halı üçün ilk sətir iki tam ədəd N ≤ 100 və K ≤ N ehtiva edir. İkinci sətir N tam ədəd, P_1, P_2, …, P_N göstərir (P_i ≤ 10). Sonrakı N sətir hər iki şəhər arasındakı uzunluqları göstərən N×N matrisi G_{1..N,1..N} təşkil edir (G_{i,j} ≤ 100), burada G_{i,j}=G_{j,i} və G_{i,i}=0 təmin edilir. Əgər G_{i,j}=-1 olarsa, bu, şəhər i ilə j arasında yol olmadığını bildirir. Hər bir halın son sətiri K tam ədəd A_1, A_2, …, A_K ehtiva edir. Başlanğıcda A_1 şəhərində olursunuz.
Çıxış verilənləri
Hər bir test halı üçün minimal vaxtı çıxış edin.