يمكن تمثيل مزرعة Farmer John برسم بياني موجه موزون، حيث تربط الطرق (الحواف) بين العقد المختلفة، ويمثل وزن كل حافة الزمن اللازم للسير على الطريق. تحب Bessie كل يوم الانتقال من الحظيرة (الموجودة عند العقدة $1$) إلى الحقول (الموجودة عند العقدة $N$)، عبر $K$ طرق بالضبط، وتريد الوصول إلى الحقول بأسرع وقت ممكن مع الالتزام بهذا القيد. لكن في مرحلة ما تتوقف صيانة الطرق، وتبدأ بالتعطل واحدًا تلو الآخر، فتصبح غير قابلة للمرور. ساعد Bessie على إيجاد أقصر مسار من الحظيرة إلى الحقول في كل لحظة!

بصيغة رسمية، نبدأ برسم بياني موجه موزون كامل ذي $N$ رؤوس ($1\le N\le 300$) و$N^2$ حواف: حافة واحدة لكل زوج $(i, j)$ حيث $1 \le i, j \le N$ (لاحظ أن هناك $N$ حلقات ذاتية). بعد كل حذف، اطبع أقل وزن لأي مسار من $1$ إلى $N$ يمر عبر $K$ حواف بالضبط (ليست بالضرورة مختلفة)، حيث ($2\le K\le 8$). لاحظ أنه بعد الحذف رقم $i$، يتبقى في الرسم البياني $N^2-i$ حواف.

يُعرَّف وزن المسار بأنه مجموع أوزان جميع الحواف فيه. لاحظ أن المسار قد يحتوي على الحافة نفسها عدة مرات وعلى الرأس نفسه عدة مرات، بما في ذلك الرأسان $1$ و$N$.

الإدخال

يحتوي السطر الأول على $N$ و$K$.

يحتوي كل من الأسطر $N$ التالية على $N$ أعداد صحيحة. العدد رقم $j$ في السطر رقم $i$ هو $w_{ij}$ ($1\le w_{ij}\le 10^8$).

بعد ذلك تأتي $N^2$ أسطر إضافية، يحتوي كل منها على عددين صحيحين $i$ و$j$ ($1\le i,j\le N$). يظهر كل زوج من الأعداد الصحيحة مرة واحدة بالضبط.

الإخراج

اطبع $N^2$ أسطر بالضبط، يمثل كل منها أقل وزن لمسار ذي $K$ حواف بعد كل حذف. إذا لم يوجد مسار ذو $K$ حواف، فاطبع $-1$.

أمثلة

الإدخال 1

3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2

الإخراج 1

11
18
22
22
22
-1
-1
-1
-1

ملاحظة

بعد الحذف الأول، أقصر مسار ذي $4$ حواف هو:

1 -> 2 -> 3 -> 2 -> 3

بعد الحذف الثاني، أقصر مسار ذي $4$ حواف هو:

1 -> 3 -> 2 -> 1 -> 3

بعد الحذف الثالث، أقصر مسار ذي $4$ حواف هو:

1 -> 3 -> 3 -> 3 -> 3

بعد ست عمليات حذف، لم يعد هناك مسار ذو $4$ حواف.

المهام الفرعية

• لكل $2\le T\le 14$، تحقق حالة الاختبار $T$ الشرط $K=\lfloor (T+3)/2\rfloor$.

مؤلف المسألة: Benjamin Qi