תיאור הבעיה

האם אתם מכירים את חברת Just Odd Inventions? עיסוקה של חברה זו הוא ליצור "סתם המצאות מוזרות (just odd inventions)". כאן נקרא לה בקיצור חברת JOI.

לחברת JOI יש $2$ משרדים, וכל משרד מורכב מחדרים ריבועיים בגודל זהה המסודרים בצורת רשת. בין כל שני חדרים הגובלים זה בזה בצלע ישנה דלת המצוידת במנגנון אימות באמצעות תעודת מזהה. מאחר שחברת JOI מטפלת במידע מסווג ברמות שונות, לכל חדר מוגדר מספר שלם חיובי הנקרא רמת סיווג, ולא ניתן להיכנס לחדר אלא אם רמת האימות (מספר שלם אי-שלילי המוגדר בתעודה עבור אותו משרד) גדולה או שווה לרמת הסיווג של החדר. הכניסה והיציאה היחידה של כל משרד היא מבואת המעליות היחידה שלו, ורמת הסיווג של חדר מבואת המעליות היא הנמוכה ביותר, כלומר $1$. כאשר רמת האימות עבור אותו משרד היא $0$, לא ניתן אפילו להיכנס למבואת המעליות.

בחברת JOI, בעקבות הצעה פתאומית של נשיא החברה, הוחלט לערוך סיור לקהל הרחב לביקור בתוך החברה. עליכם להחליט על שילוב רמות האימות בתעודה שתימסר למבקרים. בכל פעם שמבקר מוצא דלת שניתן לפתוח, הוא תמיד פותח אותה ונכנס פנימה (אפשר גם לבקר באותו חדר מספר רב של פעמים). משום כך, אינכם רוצים לקבוע את רמות האימות בתעודה של המבקרים גבוה מהנדרש. אולם, כדי להפוך את הסיור לאטרקטיבי, הסיור חייב לאפשר למבקרים לבקר בסך הכול בלפחות $R$ חדרים ב-$2$ המשרדים יחד, כולל חדרי מבואות המעליות. אם רמות האימות בתעודה ייקבעו נמוך מדי, ייתכן שלא ניתן יהיה לעמוד בתנאי זה.

לחברת JOI יש $2$ משרדים, והחדרים במשרד ה-$k$ ($k = 1, 2$) מסודרים כך שישנם $W_k$ חדרים בכיוון מזרח-מערב ו-$H_k$ חדרים בכיוון צפון-דרום, ובסך הכול $W_k \times H_k$ חדרים. נסמן את החדר ה-$i$ ממערב וה-$j$ מצפון במשרד ה-$k$ ב-$(i, j)_k$.

בהינתן הערכים של $W_k$, $H_k$ ו-$R$, מיקום מבואת המעליות $(X_k, Y_k)_k$ ורמת הסיווג של כל חדר, כתבו תוכנית המוצאת את הערך המינימלי האפשרי של סכום רמות האימות בתעודת המבקר כך שהמבקר יוכל לבקר בלפחות $R$ חדרים בסך הכול ב-$2$ המשרדים.

דרך אגב, האופן שבו חברת JOI מפיקה רווחים מיצירת "סתם המצאות מוזרות" הוא סודי ביותר אפילו בתוך החברה, ואיש אינו יודע זאת מלבד נשיא החברה.

קלט

• בשורה ה-$1$ כתוב מספר שלם חיובי $R$ ($1 \le R \le 100000$).
• מהשורה ה-$2$ ואילך ניתנים לפי הסדר הנתונים של $2$ המשרדים.
• הנתונים של כל משרד ניתנים כך שבשורה הראשונה כתובים המספרים השלמים החיוביים $W_k, H_k, X_k, Y_k$ ($1 \le X_k \le W_k \le 500, 1 \le Y_k \le H_k \le 500$), ואחריהם $H_k$ שורות שבהן המספר ה-$i$ בשורה ה-$j$ הוא מספר שלם $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) המייצג את רמת הסיווג של החדר $(i, j)_k$.
• כמו כן מתקיים $R \le W_1 \times H_1 + W_2 \times H_2$.

מתוך נתוני הבדיקה, עבור $30\%$ מהניקוד מתקיים $R, W_k, H_k \le 100$.

פלט

הדפיסו שורה $1$ בלבד המכילה את הערך המינימלי המבוקש של סכום רמות האימות בתעודה.

Sample 1

5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 3

15

Sample 2

8
5 4 1 3
5 5 4 5 5
8 2 1 9 7
1 1 3 5 1
7 2 7 1 3
6 5 6 2
2 3 5 8 2 7
1 6 9 4 5 1
2 4 5 4 2 2
5 4 2 5 3 3
7 1 5 1 5 6

4

Sample 3

6
3 3 2 2
2 9 2
9 1 9
2 9 2
2 2 1 1
1 3
5 7

9

הסבר לדוגמאות

בדוגמה 1, אם קובעים את רמות האימות בתעודה הנמסרת למבקר כך שרמת האימות עבור משרד $1$ היא $9$ ורמת האימות עבור משרד $2$ היא $6$, המבקר יכול לבקר ב-$5$ חדרים (החדרים $(1, 1)_1, (1, 2)_1, (2, 1)_1$ במשרד $1$, והחדרים $(1, 1)_2, (2, 1)_2$ במשרד $2$). במקרה זה, סכום רמות האימות הוא $15$. זהו הערך המינימלי של סכום רמות האימות הנדרש כדי שניתן יהיה לבקר בסך הכול בלפחות $5$ חדרים.

בדוגמה 3, אם קובעים את רמות האימות בתעודה הנמסרת למבקר כך שרמת האימות עבור משרד $1$ היא $9$ ורמת האימות עבור משרד $2$ היא $0$, המבקר יכול לבקר ב-$9$ חדרים (החדרים $(1, 1)_1, (1, 2)_1, (1, 3)_1, (2, 1)_1, (2, 2)_1, (2, 3)_1, (3, 1)_1, (3, 2)_1, (3, 3)_1$ במשרד $1$). במשרד $2$ לא ניתן לבקר אפילו בחדר $1$ (אפילו לא ניתן להיכנס למבואת המעליות $(1, 1)_2$). במקרה זה, סכום רמות האימות הוא $9$. זהו הערך המינימלי של סכום רמות האימות הנדרש כדי שניתן יהיה לבקר בסך הכול בלפחות $6$ חדרים.