Задача C1. Комната ярости (2 балла)


Гертруда имеет n тарелок. И хочет разбить их все. По одной. Но тарелки бьются очень звонко. Она опасается, что повредит слух.

Известно, что сила звона первой разбитой тарелки будет равна a1. Сила звона каждой последующей разбитой тарелки будет в b раз больше силы звона предыдущей. То есть сила звона i-ой (i>1) разбитой тарелки будет равна ai=ai−1⋅b.

Гертруда знает максимальное суммарное значение сил звона MAX, которое могут выдержать её уши, и желает максимально насладиться звуками бьющейся посуды.

Помогите Гертруде, найдите максимальное количество тарелок, которые она может разбить, не повредив слух. И побыстрее.

Формат входных данных

В первой строке вводятся четыре целых числа n, a1, b, MAX (1≤n,MAX≤100,1≤a1,b≤10).

Формат выходных данных

Выведите максимальное количество тарелок.

Пояснение к примеру

Если Гертруда разобьёт одну тарелку, то суммарное значение сил звона будет равно a1=1.

Если разобьёт две тарелки, то суммарное значение будет равно a1+a2=1+2=3.

Если разобьёт три, то – a1+a2+a3=1+2+4=7.

Sample Input:

10 1 2 4
Sample Output:
2
Напишите программу. Тестируется через stdin → stdout
Time Limit: 2 секунды
Memory Limit: 256 MB