ניתן לייצג את החווה של 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