โจทย์ปัญหา

คุณรู้จักบริษัท 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$ นับจากทิศเหนือด้วย $(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$ ห้อง