Super Mario
Национална Олимпиада по Информатика, Контролно 3
Time Limit: 0.4s, Memory Limit: 32MiB
Ели е играе модифицирана версия на играта Super Mario. В нея трябва да се премине над N клетки, потенциално стъпвайки на някои от тях, като се започва преди най-лявата и се завършва, когато се отиде след най-дясната. На всеки ход играчът може единствено да скача на разстояние от 1 до K клетки надясно от текущата. Стъпвайки в дадена клетка се заплаща дадена цена Ci, която се знае предварително за всяка клетка.

Нека, например, нивото има шест клетки с цени (от ляво надясно): (2, 3, 6, 1, 2, 7) и максимален скок K = 2. В първия ход може да се скочи само на първата или втората клетка (съответно, заплащайки 2 или 3). Ели би избрала втората клетка, заплащайки по-голямата цена, но отивайки по-надясно. Следващият скок на момичето е на четвъртата (заплащайки цена 1), после на петата (заплащайки цена 2) и накрая да извън дъската. Така сумарната цена би била 6, което е и минимумът, който момичето може да постигне за това ниво.

Ели иска да постави рекорди на всички нива на играта, за да впечатли Станчо. Помогнете й, като напишете програма, която намира цената на оптималния път.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – съответно броят клетки на полето и максималната дължина на скока. На следващия ред са зададени целите числа F, A, B, и M. Те се използват за генерирането на цените на всяка от клетките. Първата клетка C1 = F, а за всяко i = 2 ... N, Ci = (Ci-1 * A + B) % M.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималната сума, която Ели трябва да заплати за да премине даденото ниво.
Ограничения
  • 1 ≤ N ≤ 10,000,000
  • 1 ≤ K ≤ 1,000,000
  • 0 ≤ F, A, B < M ≤ 1,000,000,007
Примерен Вход Примерен Изход
20 5 7 3 8 23 18
Числата, които има на клетките, са (от ляво надясно): (7, 6, 3, 17, 13, 1, 11, 18, 16, 10, 15, 7, 6, 3, 17, 13, 1, 11, 18, 16). Оптималният път е през клетките с индекси 3 (+3), 6 (+1), 10 (+10), 14 (+3), 17 (+1), след което скачаме навън. Така получаваме отговор 18.
Мрън!