Na fabrike funkcioniruet proizvodstvennaja linija. Obrabotka kazhdoj detali trebuet dvuh operacij: snachala vypolnjaetsja operacija "A", a zatem - operacija "V". Dlja vypolnenija kazhdoj iz operacij suschestvuet opredelennoe kolichestvo stankov. Na ris.1 priveden primer organizacii proizvodstvennoj linii, kotoraja rabotaet sledujuschim obrazom. Stanok, vypolnjajuschij operaciju "A", beret detal' iz vhodnogo kontejnera, ispolnjaet operaciju "A" i pomeschaet detal' v promezhutochnyj kontejner. Stanok, vypolnjajuschij operaciju "V", beret detal' iz promezhutochnogo kontejnera, ispolnjaet operaciiju "V" i pomeschaet detal' v vyhodnoj kontejner. Vse stanki rabotajut parallel'no i nezavisimo drug ot druga. Vmestimost' kazhdogo iz kontejnerov neogranichena. Stanki imejut razlichnye vremennye harakteristiki obrabotki detalej, kazhdyj stanok imeet svoe vremja obrabotki.

Napishite programmu, kotoraja opredeljaet minimal'nyj period vremeni, neobhodimyj dlja vypolnenija operacii "A" nad vsemi N detaljami pri uslovii, chto oni stanovjatsja dostupnymi v moment vremeni 0 (podzadacha A). Neobhodimo takzhe vychislit' minimal'nyj period vremeni, neobhodimyj dlja vypolnenija obeih operacij "A" i "V" nad vsemi N detaljami (podzadacha V).

Vhodnye dannye

Fajl INPUT.TXT sostoit iz pjati strok i soderzhit nabor celyh polozhitel'nyh chisel. V pervoj stroke soderzhitsja chislo N - kolichestvo detalej (1<=N<=1000). Vo vtoroj stroke nahoditsja chislo M1 - kolichestvo stankov, vypolnjajuschih operaciju "A" (1<=M1<=30). V tret'ej stroke soderzhatsja M1 celyh chisel, opredeljajuschih vremena obrabotki detali sootvetstvujuschimi stankami, vypolnjajuschimi operaciju "A". V chetvertoj i pjatoj strokah nahodjatsja sootvetstvenno chislo M2 - kolichestvo stankov, vypolnjajuschih operaciju "V" (1<=M2<=30), i M2 celyh chisel, opredeljajuschih vremena obrabotki detali sootvetstvujuschimi stankami. Vremja obrabotki detali na kazhdom stanke vkljuchaet vremja, neobhodimoe dlja peremeschenija detali iz kontejnera k stanku i so stanka v kontejner. Vremja obrabotki dlja kazhdogo stanka zadaetsja celym chislom ot 1 do 20.

Vyhodnye dannye

Vasha programma dolzhna sformirovat' dve stroki v fajle OUTPUT.TXT. Pervaja stroka dolzhna soderzhat' odno polozhitel'noe celoe chislo: reshenie podzadachi A. Vtoraja stroka dolzhna soderzhat' reshenie podzadachi V.

Primer vvoda i vyvoda

Nizhe priveden primer vhodnogo fajla i primer sootvetstvujuschego emu vyhodnogo fajla.

INPUT.TXT	OUTPUT.TXT
5 2 1 1 3 3 1 4	3 5

Posle neverojatnogo uspeha golovomki "Kubik Rubika", gospodin Rubik pridumal ee ploskij variant - "Magicheskie kvadratiki". Golovolomka sostoit iz 8 svjazannyh mezhdu soboj odinakovyh kvadratikov (sm. ris.1). Jeti kvadratiki raskrasheny v 8 razlichnyh cvetov. Cveta opredeljajutsja celymi chislami ot 1 do 8, kak pokazano na ris.1. Konfiguracija golovolomki opredeljaetsja posledovatel'nost'ju cvetov kvadratikov, zadannyh po chasovoj strelke, nachinaja s levogo verhnego kvadrata i konchaja levym nizhnim. Naprimer, konfiguracija na ris.1 opredeljaetsja posledovatel'nost'ju (1, 2, 3, 4, 5, 6, 7, 8). Jeta konfiguracija vsegda javljaetsja nachal'noj.

Suschestvujut tri bazovyh preobrazovanija golovolomki. Jeti preobrazovanija oboznachajutsja bukvami A, B i C:

A -- perestanovka verhnego i nizhnego rjadov;
B -- ciklicheskij sdvig vpravo na odin kvadrat;
C -- povorot po chasovoj strelke chetyreh srednih kvadratikov na 90 gradusov.

Izvestno, chto s ispol'zovaniem jetih preobrazovanij mozhno poluchit' ljubuju zadannuju konechnuju konfiguraciju.

Realizacii bazovyh preobrazovanij dlja nachal'noj konfiguracii privedeny na ris.2. Chisla, raspolozhennye vne kvadratikov, opredeljajut pozicii kvadratikov. Esli kvadratik v pozicii p soderzhit chislo i, jeto oznachaet, chto v rezul'tate sootvetstvujuschego preobrazovanija kvadratik, kotoryj v nachal'noj konfiguracii nahodilsja v pozicii i peremeschaetsja v poziciju p.

Ris.2: Bazovye preobrazovanija

Napishite programmu, kotoraja nahodit posledovatel'nost' dejstvij, preobrazujuschuju nachal'nuju konfiguraciju (sm. ris. 1) v zadannuju konechnuju konfiguraciju (podzadacha A).

Dva dopolnitel'nyh balla za kazhdyj test budut prisuzhdat'sja v tom sluchae, esli dlina posledovatel'nosti preobrazovanij ne prevyshaet 300 (podzadacha B).

Vhodnye dannye

Fajl ishodnyh dannyh INPUT.TXT soderzhit 8 polozhitel'nyh celyh chisel, nahodjaschihsja v pervoj stroke fajla. Jeti chisla zadajut konechnuju konfiguraciju golovolomki.

Vyhodnye dannye

V pervoj stroke fajla OUTPUT.TXT dolzhno soderzhat'sja chislo L - dlina posledovatel'nosti preobrazovanij. Sledujuschie L strok dolzhny soderzhat' najdennuju posledovatel'nost' preobrazovanij. V kazhdoj stroke v pervoj pozicii dolzhna soderzhat'sja odna iz bukv "A", "B" ili "C", zadajuschaja sootvetstvujuschee preobrazovanie.

Dopolnitel'nye sredstva

V vashe rasporjazhenie predostavljaetja programma MTOOL.EXE (in task directory), kotoraja pozvoljaet smodelirovat' rabotu golovolomki. Programma MTOOL.EXE imeet sledujuschij format vyzova: "mtool input.txt output.txt", gde formaty fajlov input.txt i output.txt sootvetstvujut opisannym trebovanijam. S pomosch'ju jetoj programmy vy smozhete jeksperimentirovat' s konechnoj konfiguraciej i s posledovatel'nost'ju preobrazovanij.

Primer vvoda i vyvoda

INPUT.TXT	OUTPUT.TXT
2 6 8 4 5 7 3 1	7 B C A B C C B