A híd

n ember szeretne átkelni egy hídon éjszaka. Legfeljebb két ember kelhet át egyszerre, akiknél lennie kell egy elemlámpának. Az n embernél csak egy elemlámpa van, így egyfajta ingázást kell végezniük, hogy visszajuttassák az elemlámpát, és ezáltal további emberek is átkelhessenek.

Az egyes személyek nem feltétlenül azonos sebességgel tudnak átkelni a hídon; egy csoport sebességét a lassabb tagjának a sebessége határozza meg. A feladatod, hogy meghatározz egy olyan stratégiát, amellyel az n ember minimális idő alatt juthat át a túloldalra.

A bemenet specifikációja

A bemenet egy olyan sorral kezdődik, amely egyetlen pozitív egész számból, a tesztesetek számából áll. Ezt a sort egy üres sor követi, mint ahogy egy-egy üres sor van két egymást követő teszteset között is.

Minden teszteset első sorában n értéke szerepel. Ezt n sor követi, amelyek az egyes emberek átkelési idejeit tartalmazzák. Legfeljebb 1000 ember lesz, és egyiküknek sem tart tovább 100 másodpercnél a hídon való átkelés.

A kimenet specifikációja

Az egyes tesztesetekhez tartozó kimeneteknek az alábbi leírást kell követniük. Két egymást követő teszteset kimenetét egy-egy üres sorral kell elválasztani.

Minden tesztesetre a kimenet első sorában az n ember átkeléséhez szükséges másodpercek számának kell szerepelnie. A további sorokba egy olyan stratégiát kell kiírni, amellyel ez az idő érhető el. Mindegyik további sornak egy vagy két egész számot kell tartalmaznia, amelyek a következőnek átkelő személyt vagy személyeket adják meg. (Az egyes személyeket a bemeneten megadott átkelési idejükkel azonosítjuk. Bár több embernek is lehet ugyanaz az átkelési ideje, ennek a kétértelműségnek nincs következménye.) Ne feledjük, hogy az átkelések váltakozó irányúak, mivel mindig vissza kell juttatni az elemlámpát, hogy mások is átkelhessenek. Ha több stratégiával is elérhető a minimális idő, bármelyik megadható.

Példa bemenet

1. 1
3. 4
4. 1
5. 2
6. 5
7. 10

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 17
2. 1 2
3. 1
4. 5 10
5. 2
6. 1 2

letöltés szöveges állományként