Есептің шарты

Сіз Just Odd Inventions компаниясын білесіз бе? Бұл компанияның қызметі — «жай ғана оғаш өнертабыстар (just odd inventions)» жасау. Мұнда біз оны қысқаша JOI компаниясы деп атаймыз.

JOI компаниясының $2$ кеңсесі бар, және олардың әрқайсысы тор тәрізді қатарласып орналасқан өлшемдері бірдей шаршы бөлмелерден тұрады. Қабырғалары арқылы шектесетін барлық бөлмелердің арасында жеке куәлік арқылы аутентификациялау функциясы бар есік орнатылған. JOI компаниясы әртүрлі деңгейдегі құпия ақпаратпен жұмыс істейтіндіктен, әр бөлме үшін құпиялылық деңгейі деп аталатын оң бүтін сан белгіленген, және жеке куәлікте сол кеңсе үшін белгіленген теріс емес бүтін аутентификация деңгейі бөлменің құпиялылық деңгейінен кем болмаса ғана сол бөлмеге кіруге болады. Әр кеңсенің жалғыз кіріп-шығатын жері — жалғыз лифт холы ғана, ал лифт холы бөлмесінің құпиялылық деңгейі ең төменгі $1$-ге тең. Сол кеңсе бойынша аутентификация деңгейі $0$ болған кезде лифт холына да кіру мүмкін емес.

JOI компаниясында президенттің аяқ астынан жасаған ұсынысы бойынша қарапайым адамдарға компания ішін аралату үшін тур өткізу туралы шешім қабылданды. Сізге келушілерге берілетін жеке куәліктегі аутентификация деңгейлерінің комбинациясын таңдау қажет. Келуші ашылатын есікті көрсе болды, міндетті түрде оны ашып ішке кіреді (бір бөлмеге бірнеше рет кіруге де болады). Сондықтан сіз келушілердің жеке куәлігіндегі аутентификация деңгейін қажетті деңгейден артық көтергіңіз келмейді. Алайда турды тартымды ету үшін, тур барысында лифт холының бөлмелерін қоса алғанда, $2$ кеңседе барлығы кемінде $R$ бөлмеге кіруге мүмкіндік болуы керек. Егер жеке куәліктің аутентификация деңгейін тым төмендетіп жіберсеңіз, бұл шарт орындалмай қалуы мүмкін.

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$ және әр бөлменің құпиялылық деңгейі берілгенде, келуші $2$ кеңседе барлығы кемінде $R$ бөлмеге кіре алуы үшін келушінің жеке куәлігіндегі аутентификация деңгейлерінің қосындысының ең кіші мүмкін мәнін табатын программа жазыңыз.

Айтпақшы, 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$ жолдың $j$-ші жолының $i$-ші орнында $(i, j)_k$ бөлмесінің құпиялылық деңгейін білдіретін бүтін $L_{k, i, j}$ ($1 \le L_{k, i, j} < 100000000 = 10^8$) саны ретінде беріледі.
• Сонымен қатар, $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, (1, 2)_1, (2, 1)_1$ бөлмелеріне және $2$-ші кеңсенің $(1, 1)_2, (2, 1)_2$ бөлмелеріне) кіре алады. Бұл кезде аутентификация деңгейлерінің қосындысы $15$ болады. Бұл барлығы кемінде $5$ бөлмеге кіре алу үшін қажетті аутентификация деңгейлерінің қосындысының ең кіші мәні.

3-мысалда келушіге берілетін жеке куәліктің аутентификация деңгейін $1$-ші кеңсенің аутентификация деңгейі $9$, ал $2$-ші кеңсенің аутентификация деңгейі $0$ болатындай етіп орнатса, келуші $9$ бөлмеге ($1$-ші кеңсенің $(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$ бөлмелеріне) кіре алады. $2$-ші кеңсенің $1$ де бөлмесіне кіре алмайды (тіпті $(1, 1)_2$ лифт холына да кіре алмайды). Бұл кезде аутентификация деңгейлерінің қосындысы $9$ болады. Бұл барлығы кемінде $6$ бөлмеге кіре алу үшін қажетті аутентификация деңгейлерінің қосындысының ең кіші мәні.