Het shuttlebedrijf organiseert een wedstrijd: één gouden munt voor iedereen die het vroegste tijdstip kan vinden waarop de bus met het eerste ID-nummer vertrekt en elke bus met het volgende ID-nummer op de volgende minuut vertrekt. (Hiervoor is de eerste regel van je aantekeningen niet langer relevant.)

Stel bijvoorbeeld dat je dezelfde reeks ID-nummers hebt als hiervoor:

7,13,x,x,59,x,31,19

Een x in de busdienst betekent dat er geen beperkingen zijn voor het ID-nummer van de bus die op dat moment moet vertrekken.

Dit betekent dat je zoekt naar het vroegste tijdstip (t genaamd) waarop:

De enige busritten die er toe doen, zijn die van bussen met de vermelde ID-nummers op hun specifieke offsets vanaf tijdstip t. Die bussen kunnen op andere tijdstippen vertrekken, en bussen met andere ID-nummers kunnen op dezelfde tijdstippen vertrekken. Kijken we bijvoorbeeld naar bovenstaande reeks: omdat de bus met ID-nummer 19 zeven minuten na de bus met ID-nummer 7 moet vertrekken, zal de bus met ID-nummer 7 ook altijd vertrekken met de bus met ID-nummer 19 om zeven minuten na tijdstip t.

In dit voorbeeld is 1068781 het vroegste tijdstip waarop dit gebeurt:

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

In het bovenstaande voorbeeld vertrekt de bus met ID-nummer 7 op tijdstip 1068788 (zeven minuten na tijdstip t). Dat is goed. De enige vereiste op die minuut is dat de bus met ID-nummer 19 dan vertrekt, en dat gebeurt ook.

Hier zijn nog enkele andere voorbeelden:

Met zoveel bussen in de reeks moet er beslist wel een vroegste tijdstip zijn dat groter is dan 100000000000000!

Opgave

Wat is het vroegste tijstip waarop alle bussen met vermelde ID-nummers vertrekken met offsets die overeenkomen met hun posities in de reeks? Hiervoor ga je als volgt te werk:

Voorbeeld

> earliest_timestamp("7,13,x,x,59,x,31,19")
1068781
> earliest_timestamp("17,x,13,19")
3417
> earliest_timestamp("67,7,59,61")
754018
> earliest_timestamp("67,x,7,59,61")
779210
> earliest_timestamp("67,7,x,59,61")
1261476
> earliest_timestamp("1789,37,47,1889")
1202161486