Cheerio Contest 2 P2 - Cereal Boxes

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 256M

Problem type

Farmer Bob is buying cereal boxes at his local grocery store, which are priced in the following way:

  • The first M cereal boxes cost C dollars each
  • For every M boxes purchased, the price of any subsequent boxes is increased by I dollars

Bob only has Q dollars to spend. What is the maximum number of cereal boxes he can buy?


For all subtasks:

  • 1 \le M, C, I \le 10^9
  • 1 \le Q \le 10^{12}

Input Specification

The only line of input contains four integers M, C, I and Q.

Output Specification

Output the maximum number of cereal boxes Bob can buy.

Sample Input 1

2 1 3 35

Sample Output 1


Explanation for Sample 1

The prices of the cereal boxes Bob can buy are 1, 1, 4, 4, 7, 7 and 10 dollars respectively.

Sample Input 2

1 15 1 10

Sample Output 2



There are no comments at the moment.