README.md

Зеленчуци

Условие

Помните ли великия ловец на съкровища Въпци, който плячкоса пирамидите на Ильоменатите? Сега се излежава в някой хамак на Хаваите и си харчи парите от съкровищата. Но Въпци не винаги е бил богат и не винаги е бил ловец на съкровища. Като млад е живял на село при баба си и ѝ е помагал да се грижат за лехите в градината. Градината им има две лехи (първата с R1 реда и C1 колони, втората с R2 реда и C2 колони), но баба му иска да я разширят. Нейният план е Въпци да обере зеленчуците от двете лехи, като тръгне от горния ляв ъгъл на всяка и се движи само надолу или надясно (няма време да берe цялата леха), като обира всички зеленчуци по пътя си, докато не излезе през долния десен ъгъл. След като Въпци обере двете лехи (X от първата и Y от втората), ще могат да насадят трета леха, в която ще има толкова зеленчуци, колкото е стойността на X^Y % 10037. След това ще могат да насадят и четвърта, която ще има толкова зеленчуци, колкото има втората леха на степен зеленчуците от третата, разделен по модул на 10037. N-тата поредна (за N > 2) леха ще има (зеленчуците от N - 2 лехата)^{(зеленчуците от N - 1 лехата)} % 10037. Напишете програма, която по дадени начални лехи и номер на леха N изкарва на конзолата броят зеленчуци, които би имала лехата с номер N, ако Въпци е обрал зеленчуците от първите две лехи по оптимален начин.

Вход

• На първия ред има две числа R и C - броят редове и колони на лехата
• На всеки от следващите R реда ще има C числа - броят зеленчуци, които се намират във всяка клетка от лехата
• Информацията за втората леха ще бъде в същия формат
• На последният ред се намира числото N - поредния номер на лехата, чието количество зеленчуци трябва да отпечатате

Изход

• Трябва да отпечатате едно единствено число - броят зеленчуци, които ще има в N-тата леха

Ограничения

• 1 <= N <= 10000
• 1 <= R, C <= 800
• Количеството зеленчуци на дадено място в началните лехи винаги ще бъде между 0 и 100, включително
• Лимит за памет: 16 MiB
• Лимит за време: 0.2 секунди

Примери

Вход

3 3
1 2 3
1 4 5
7 8 1
2 2
1 2
3 4
1

Изход

18

Обяснение

• N1 = 1 + 1 + 7 + 8 + 1 = 18

Вход

2 2
0 2
3 1
2 3
1 1 2
2 0 1
4

Изход

9277

Обяснение

• Първата леха:

0 2
3 1

• Втората леха:

1 1 2
2 0 1

• N1 = 0 + 3 + 1 = 4
• N2 = 1 + 1 + 2 + 1 = 5
• N3 = 4⁵ % 10037 = 1024
• N4 = 5¹⁰²⁴ % 10037 = 9277