Đề bài

Bạn có biết công ty Just Odd Inventions không? Công việc kinh doanh của công ty này là tạo ra "những phát minh kỳ quặc (just odd inventions)". Ở đây chúng ta gọi tắt là công ty JOI.

Công ty JOI có $2$ văn phòng, mỗi văn phòng được tạo thành từ các căn phòng hình vuông có cùng kích thước xếp thành dạng lưới ô vuông. Giữa mọi cặp phòng kề cạnh đều có một cánh cửa được trang bị chức năng xác thực bằng thẻ ID. Vì công ty JOI xử lý thông tin mật ở nhiều cấp độ khác nhau, mỗi căn phòng được thiết lập một số nguyên dương gọi là cấp độ bảo mật, và người ta không thể bước vào một căn phòng trừ khi cấp độ xác thực (là một số nguyên không âm được quy định riêng cho từng văn phòng trên thẻ ID) lớn hơn hoặc bằng cấp độ bảo mật của căn phòng đó. Lối ra vào duy nhất của mỗi văn phòng là sảnh thang máy duy nhất của văn phòng đó, và cấp độ bảo mật của phòng sảnh thang máy là mức thấp nhất, bằng $1$. Khi cấp độ xác thực đối với văn phòng đó bằng $0$, người ta thậm chí không thể bước vào sảnh thang máy.

Tại công ty JOI, do một đề xuất bất ngờ của giám đốc, công ty quyết định tổ chức một chuyến tham quan cho công chúng vào thăm nội bộ công ty. Bạn cần quyết định tổ hợp cấp độ xác thực trên thẻ ID sẽ phát cho khách tham quan. Khi khách tham quan tìm thấy bất kỳ cánh cửa nào có thể mở được, họ chắc chắn sẽ mở cửa và đi vào trong (cũng có thể thăm cùng một căn phòng nhiều lần). Vì lý do đó, bạn không muốn đặt cấp độ xác thực trên thẻ ID của khách tham quan cao hơn mức cần thiết. Tuy nhiên, để chuyến tham quan có sức hấp dẫn, chuyến tham quan phải cho phép khách tham quan thăm tổng cộng ít nhất $R$ căn phòng ở cả $2$ văn phòng, tính cả các phòng sảnh thang máy. Nếu hạ cấp độ xác thực trên thẻ ID xuống quá thấp, điều kiện này có thể không được thỏa mãn.

Công ty JOI có $2$ văn phòng, các căn phòng ở văn phòng thứ $k$ ($k = 1, 2$) được xếp gồm $W_k$ phòng theo hướng đông-tây và $H_k$ phòng theo hướng bắc-nam, tổng cộng có $W_k \times H_k$ phòng. Căn phòng thứ $i$ tính từ phía tây và thứ $j$ tính từ phía bắc ở văn phòng thứ $k$ được ký hiệu là $(i, j)_k$.

Cho biết giá trị của $W_k$, $H_k$ và $R$, vị trí của sảnh thang máy $(X_k, Y_k)_k$, cùng cấp độ bảo mật của từng căn phòng, hãy viết chương trình tìm giá trị nhỏ nhất của tổng cấp độ xác thực trên thẻ ID của khách tham quan để khách tham quan có thể thăm tổng cộng ít nhất $R$ căn phòng ở cả $2$ văn phòng.

Nhân tiện, làm thế nào công ty JOI kiếm được lợi nhuận từ việc tạo ra "những phát minh kỳ quặc" là bí mật tối cao ngay cả trong nội bộ công ty, và ngoài giám đốc ra thì không ai biết.

Dữ liệu vào

• Dòng thứ $1$ chứa một số nguyên dương $R$ ($1 \le R \le 100000$).
• Từ dòng thứ $2$ trở đi, dữ liệu của $2$ văn phòng lần lượt được cho.
• Dữ liệu của mỗi văn phòng gồm các số nguyên dương $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$) ở dòng đầu tiên, tiếp theo là $H_k$ dòng, trong đó số thứ $i$ ở dòng thứ $j$ là một số nguyên $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) biểu thị cấp độ bảo mật của phòng $(i, j)_k$.
• Ngoài ra, $R \le W_1 \times H_1 + W_2 \times H_2$ luôn thỏa mãn.

Trong dữ liệu chấm, đối với $30\%$ số điểm, $R, W_k, H_k \le 100$ được thỏa mãn.

Kết quả

In ra $1$ dòng duy nhất chỉ chứa giá trị nhỏ nhất của tổng cấp độ xác thực trên thẻ ID cần tìm.

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

Giải thích ví dụ

Ở Ví dụ 1, nếu cấp độ xác thực trên thẻ ID phát cho khách tham quan được thiết lập sao cho cấp độ xác thực của Văn phòng $1$ là $9$ và cấp độ xác thực của Văn phòng $2$ là $6$, khách tham quan có thể thăm $5$ căn phòng (các phòng $(1, 1)_1, (1, 2)_1, (2, 1)_1$ ở Văn phòng $1$ và các phòng $(1, 1)_2, (2, 1)_2$ ở Văn phòng $2$). Khi đó, tổng cấp độ xác thực là $15$. Đây là giá trị nhỏ nhất của tổng cấp độ xác thực để có thể thăm tổng cộng ít nhất $5$ căn phòng.

Ở Ví dụ 3, nếu cấp độ xác thực trên thẻ ID phát cho khách tham quan được thiết lập sao cho cấp độ xác thực của Văn phòng $1$ là $9$ và cấp độ xác thực của Văn phòng $2$ là $0$, khách tham quan có thể thăm $9$ căn phòng (các phòng $(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$ ở Văn phòng $1$). Không thể thăm dù chỉ $1$ căn phòng ở Văn phòng $2$ (thậm chí không thể bước vào sảnh thang máy $(1, 1)_2$). Khi đó, tổng cấp độ xác thực là $9$. Đây là giá trị nhỏ nhất của tổng cấp độ xác thực để có thể thăm tổng cộng ít nhất $6$ căn phòng.