Az egyik vállalatnál automatikusan festik a szállítószalagon érkező dobozokat. Minden dobozt a négy különböző színből a megfelelőre kell festeni. A festőgépbe csak két különböző színű tartályt lehet felszerelni egyidejűleg. Ha nem az aktuális dobozhoz tartozó színű tartály van a gépben, a tartályt a kívánt színűre kell cserélni. A színcsere művelete időigényes, ezért minimalizálni kell a cserék számát. A színcsere elvégzése az egyik felcsatolt szín leválasztása, majd a kívánt szín felkapcsolása. A tartályok fel és lekapcsolása eltérő időbe telik.
Feladat:
Írjon programot, amely meghatározza a cserékhez szükséges minimális teljes időt a megadott inputhoz.
Bemenet:
A négy használt színt az A, B, C, D betűk jelölik.
A bemenet első sorában négy 100-nál nem nagyobb egész található, amely megfelelő színű tartályok felkapcsolásához szükséges időt jelzi. A második sorban négy 100-nál nem nagyobb egész található, amely megfelelő színű tartályok lekapcsolásához szükséges időt mutatja meg. A színek sorrendje mindkét esetben A, B, C, D. A harmadik sor az N (1<=N<=10000) egész számot tartalmazza, amely a befestendő dobozok számát jelenti. Az utolsó sorban N karakter van, melyek mindegyike az A, B, C, D karakterek egyike. Munkakezdéskor az A és a B tartályok vannak felcsatolva.
Kimenet:
A kimeneti állomány első sorába egyetlen egész szám kerüljön, amely a cserékhez szükséges összidőt adja meg.
Példa:
|
paint.in |
paint.out |
|
1 2 7 1 |
28 |
(ACM SZTE csapatverseny 1998)