وصف المسألة

هل تعرف شركة 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$). ولا يمكن زيارة ولا حتى غرفة $1$ في المكتب $2$ (بل لا يمكن حتى دخول بهو المصعد $(1, 1)_2$). عندئذٍ يكون مجموع مستويات المصادقة هو $9$. وهذه هي أصغر قيمة لمجموع مستويات المصادقة للتمكن من زيارة ما لا يقل عن $6$ غرف إجمالاً.