A Végtelen Palacsintaházban véges sok palacsinta van, de végtelen sok vendég, akik szívesen megennék a palacsintákat. Amikor reggel kinyit az étterem, a végtelen sok vendég közül pontosan D előtt nem üres a tányér, a többieknek egyelőre nincs palacsintája. A D kitüntetett vendég közül az i-diknek Pi palacsinta jutott kezdetben. Mindenki másnak nulla.
Normál esetben egy vendég percenként egy palacsintát eszik. Néha azonban a főpincér speciális pillanatot hirdethet. Ilyenkor egy percre mindenki félbehagyja az evést, és a pincér egy nem üres tányérból tetszőleges számú palacsintát átrakhat egy tetszőleges vendég tányérjába.
A főpincér bármelyik percet speciálisnak nyilváníthatja, de az is lehet, hogy nem rendel el ilyen pillanatot. A speciális percek alatt pontosan egy vendégtől kerül át valamennyi palacsinta egy másikhoz.
Akkor van vége a reggelinek, ha minden palacsinta elfogyott.
Feladat
Írjunk programot, ami megadja, leghamarabb mikor lehet vége a reggelinek.
Bemenet
A bemenet első sora a tesztesetek T számát tartalmazza. Ezután T teszteset jön, mindegyikben D, a kezdetben palacsintát kapó vendég száma, majd D darab szám, az i-dik vendég palacsintáinak száma kezdetben.
Kimenet
Minden tesztesethez a minimálisan szükséges percek számát kell kiírni. Méretek1 ≤ T ≤ 100. Kis bemenet: 1 ≤ D ≤ 6. 1 ≤ Pi ≤ 9. Nagy bemenet: 1 ≤ D ≤ 1000. 1 ≤ Pi ≤ 1000.
Példa
Bemenet |
Kimenet |
3 1 3 4 1 2 1 2 1 4 | Case #1: 3 Case #2: 2 Case #3: 3
|
Tesztadatok
Címkék
A feladat forrása: Google Code Jam 2015, selejtező forduló Algoritmusok:
megoldás |