Кидання камінців по воді

Як учасник Міжнародної ліги стрибання камінців, ви щотижня подорожуєте до нового озера та змагаєтеся у конкурсі зі стрибання камінців. Мета — підкинути камінець так, щоб він зробив якомога більше стрибків; точні правила визначення переможця наведені нижче. Щоб зробити змагання цікавішими, організатори IRSL часто обирають озера з колодами, піщаними мілинами та іншими перешкодами. Вам надано "карту" озера в профіль на рівні води, як показано у верхньому рядку прикладу нижче. (Числа $\mathrm{0..29}$ під картою — лише для довідки.) Крапка (".") позначає чисту воду, де камінець може підскочити; будь-який інший символ означає певну перешкоду, яка зупинить камінець.

...=...**..#...@....:.:.:..=..    ______________________________              11111111112222222222    012345678901234567890123456789 \

Ви стоїте на лівому краю озера. Ви можете підкинути камінець так, щоб він приземлився в будь-якій позиції на озері, а потім стрибав з фіксованим інтервалом. Таким чином, кидок визначається як пара $(i,d)$, де i \geq 0 — початкова позиція приземлення, а d > 0 — відстань між стрибками. Зауважте, що $d$ має бути додатнім. Величина кидка — це кількість разів, коли камінець підскакував по воді. Довжина — це позиція останнього контакту з водою або перешкодою. Щоб порівняти два різних кидки, використовуйте такі критерії по черзі, доки не визначиться переможець: кількість стрибків (більше — краще); довжина (більше — краще); початкова позиція (більше — краще); інтервал між стрибками (менше — краще).

Для зазначеної вище карти кидок $(27,2)$ потрапляє у перешкоду на позиції $27$; його кількість стрибків — $0$, довжина — $27$. Кидок $(16,1)$ стрибає на позиціях $16$, $17$, $18$ та $19$, а потім натрапляє на перешкоду на позиції $20$; він має кількість стрибків $4$ і довжину $20$, тож перемагає кидок $(27,2)$. Кидок $(2,7)$ стрибає на позиціях $2$, $9$, $16$ та $23$, а потім вилітає за межі озера; кількість стрибків — $4$, довжина — $23$, тож він перемагає кидок $(16,1)$. Кидок $(1,4)$ стрибає на позиціях $1$, $5$, $9$, $13$, $17$, $21$, $25$ та $29$, а потім вилітає за межі озера; кількість стрибків — $8$, довжина — $29$, і це найкращий можливий кидок для цього озера.