Comandantul Zeratul trebuie să ajungă de pe planeta
Korhal pe planeta Aiur, pentru a conduce bătălia împotriva zergilor.
Harta universului se poate reprezenta printr-o matrice cu n
linii şi m coloane. Planeta Korhal se află
la coordonatele (1,1), iar planeta Aiur
la coordonatele (n,m). Zeratul trebuie
să adune o armată cât mai mare în timpul drumului. El are la dispoziţie
un vector A de lungime n
şi un vector B de lungime m,
pe baza cărora poate calcula numărul exact de unităţi ce vor fi teleportate
în fiecare celulă a matricei în momentul când ajunge el acolo. La coordonatele
(i,j) se vor afla exact A[i]*B[j]
unităţi în momentul când comandantul ajunge acolo. Nava spaţială pe
care o conduce poate efectua doar trei tipuri de manevre: A – din coordonatele (i,j)
se deplasează în coordonatele (i+1,j); B – din (i,j)
în (i,j+1); C – din (i,j)
în (i+1,j+1).
Cerinţă
Determinaţi numărul maxim de soldaţi, cu care Zeratul
poate începe bătălia (incluzând şi unităţile aflate pe Korhal şi Aiur)
şi o secvenţă de manevre prin care se poate obţine acest număr maxim.
Date de intrare
Prima linie a fişierul de intrare zeratul.in
va conţine numărul natural N.
A doua linie va conţine N
numere naturale separate prin câte un spaţiu, reprezentând vectorul A.
A treia linie va conţine numărul natural M.
A patra linie va conţine M
numere naturale separate prin câte un spaţiu, reprezentând vectorul B.
Date de ieşire
Pe prima linie a fişierului de ieşire zeratul.out
se va scrie numărul maxim de unităţi ce se poate obţine. Pe următoarele
linii se vor afla câte 100 de caractere (mai puţin ultima linie, eventual),
reprezintând un şir de manevre prin care se obţine numărul maxim.
Restricţii
2 ≤ N,M ≤ 5000
1 ≤ A[i],B[j] ≤ 100, 1 ≤ i ≤ N, 1 ≤ j ≤ M
în 10% din teste N,M ≤ 350
în 50% din teste N,M ≤ 2500
Exemple
zeratul.in
zeratul.out
Explicatie
3
1 2 3
4
4 5 6 7
78
AABBB
Matricea ce
reprezintă universul este următorul: 4 5 6 7
8 10 12 14
12 15 18 21
Drumul optim este: (1,1)(2,1)(3,1)(3,2)(3,3)(3,4)