Masala #0431

Muzqaymoq sotuvchisi o’z muzqaymoqlarini P so’mdan sotar edi, ammo xaridorlar kamligi sababli xaridorning har bir keyingi xaridi uchun qiziqarli skidka e’lon qildi, ya’ni xaridorning 2-xarid qiladigan muzqaymog’idan boshlab har bir muzqaymoq narxi o’zidan oldingi xarid qilingan muzqaymoqdan D so’mga arzon narxda sotiladi. Lekin Muzqaymoqchi ham zararga kirishni xoxlamaydi, shu sababli muzqaymoqni tan narxidan arzon sotmaydi, ya’ni skidka bo’yicha muzqaymoqning narxi M so’mdan kam chiqsa ham u shu muzqaymoqni M so’mga sotadi.

Misol uchun P=20, D = 3, M = 6 bo’lganda xaridor muzqaymoqni quyidagi narxlarda sotib olishi mumkin:

• 1-muzqaymoq 20 so’m
• 2-muzqaymoq 17 so’m
• 3-muzqaymoq 14 so’m
• 4-muzqaymoq 11 so’m
• 5-muzqaymoq 8 so’m
• 6-muzqaymoq 6 so’m
• 7-muzqaymoq 6 so’m
• …
• \(N(N \ge 6)\) - muzqaymoq 6 so’m

Xaridorda S so’m pul bor, u nechtagacha muzqaymoq xarid qila olishini aniqlang

Kirish faylining yagona satrida to’rtta butun son, \(P(1 \le P \le 100)\), \(D(1 \le D \le 100)\), \(M(1 \le M \le 100)\) va \(S(1 \le S \le 10000)\) sonlari beriladi.

Chiqish faylida S so’m puli bor xaridor ko’pi bilan nechtagacha muzqaymoq xarid qila olishini chop eting.