Bạn có biết công ty Just Odd Inventions không? Công việc của công ty này là tạo ra “những phát minh kỳ lạ”. Ta gọi tắt công ty là JOI.

JOI có hai văn phòng. Mỗi văn phòng gồm các căn phòng hình vuông cùng kích thước, được xếp thành một lưới. Giữa hai phòng có chung cạnh luôn có một cánh cửa kiểm tra thẻ căn cước. Mỗi phòng được gán một mức độ bảo mật là số nguyên dương. Thẻ căn cước có một mức xác thực riêng cho từng văn phòng, là số nguyên không âm. Chỉ khi mức xác thực đối với văn phòng đó lớn hơn hoặc bằng mức độ bảo mật của một phòng thì người mang thẻ mới được vào phòng ấy.

Mỗi văn phòng chỉ có một lối ra vào, nằm tại phòng sảnh thang máy. Mức độ bảo mật của phòng này là \(1\), mức thấp nhất. Nếu mức xác thực đối với một văn phòng bằng \(0\) thì người mang thẻ không thể vào cả sảnh thang máy của văn phòng đó.

Theo một đề xuất bất ngờ của giám đốc, JOI sẽ tổ chức các chuyến tham quan công ty cho công chúng. Bạn phải quyết định hai mức xác thực trên thẻ phát cho khách. Khách sẽ mở cửa và đi vào mỗi khi gặp một cánh cửa mà họ được phép mở; một phòng có thể được ghé thăm nhiều lần. Vì vậy, bạn không muốn cấp mức xác thực cao hơn mức cần thiết. Tuy nhiên, để chuyến tham quan đủ hấp dẫn, khách phải có thể đến được tổng cộng ít nhất \(R\) phòng khác nhau trong hai văn phòng, tính cả các phòng sảnh thang máy có thể vào được.

Văn phòng thứ \(k\) (\(k=1,2\)) có \(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 \(W_kH_k\) phòng. Ký hiệu \((i,j)_k\) là phòng thứ \(i\) tính từ phía tây và thứ \(j\) tính từ phía bắc trong văn phòng \(k\). Sảnh thang máy ở vị trí \((X_k,Y_k)_k\).

Một phòng được tính là có thể ghé thăm nếu khách có thể đi từ sảnh thang máy đến phòng đó qua các phòng được phép vào, mỗi bước đi qua cửa nối hai phòng chung cạnh. Bạn có thể cấp mức xác thực \(0\) cho một văn phòng để khách không vào văn phòng đó.

Yêu cầu

Cho kích thước hai văn phòng, vị trí các sảnh thang máy, mức độ bảo mật của từng phòng và số \(R\). Tìm tổng nhỏ nhất của hai mức xác thực sao cho khách có thể ghé thăm ít nhất \(R\) phòng khác nhau trong hai văn phòng.

Còn JOI kiếm lợi nhuận như thế nào từ “những phát minh kỳ lạ” thì ngay trong công ty cũng là bí mật tuyệt đối, chỉ giám đốc biết.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa số nguyên \(R\).
• Tiếp theo là dữ liệu của văn phòng \(1\), rồi dữ liệu của văn phòng \(2\).
• Dữ liệu của văn phòng \(k\) bắt đầu bằng một dòng chứa bốn số nguyên \(W_k,H_k,X_k,Y_k\) cách nhau bởi dấu cách.
• Sau đó là \(H_k\) dòng, mỗi dòng chứa \(W_k\) số nguyên cách nhau bởi dấu cách. Số thứ \(i\) trên dòng thứ \(j\) trong số này là \(L_{k,i,j}\), mức độ bảo mật của phòng \((i,j)_k\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng nhỏ nhất của hai mức xác thực thỏa mãn yêu cầu.

Ràng buộc

• \(1\le R\le 100\,000\).
• \(1\le X_k\le W_k\le 500\) với \(k=1,2\).
• \(1\le Y_k\le H_k\le 500\) với \(k=1,2\).
• \(1\le L_{k,i,j}<10^8\).
• Mức độ bảo mật của mỗi sảnh thang máy bằng \(1\).
• \(R\le W_1H_1+W_2H_2\).
• Hai mức xác thực cần chọn là các số nguyên không âm.
• Giới hạn thời gian: \(2\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(30\%\) số điểm (\(6\) điểm) ứng với các bộ dữ liệu thỏa mãn \(R\le 100\), \(W_k\le 100\) và \(H_k\le 100\) với cả \(k=1,2\).

Ví dụ

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

15

Chọn mức xác thực \(9\) cho văn phòng \(1\) và \(6\) cho văn phòng \(2\). Khách có thể ghé thăm \(5\) phòng: \((1,1)_1\), \((1,2)_1\), \((2,1)_1\) ở văn phòng \(1\) và \((1,1)_2\), \((2,1)_2\) ở văn phòng \(2\). Tổng hai mức xác thực bằng \(15\), là tổng nhỏ nhất để có thể ghé thăm ít nhất \(5\) phòng.

Trong hình dưới đây, văn phòng \(1\) ở bên trái, văn phòng \(2\) ở bên phải; các phòng khách có thể ghé thăm được tô xám.

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

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

9

Chọn mức xác thực \(9\) cho văn phòng \(1\) và \(0\) cho văn phòng \(2\). Khách có thể ghé thăm toàn bộ \(9\) phòng của văn phòng \(1\), nhưng không thể vào bất kỳ phòng nào ở văn phòng \(2\), kể cả sảnh thang máy \((1,1)_2\). Tổng hai mức xác thực bằng \(9\), là tổng nhỏ nhất để có thể ghé thăm ít nhất \(6\) phòng.