25879번 - Chocolate Gifts 다국어

This is Timothy’s last semester here at UCF, and he is determined to finish college as the most favorite Knight ever! With his “extensive” friendship knowledge, he has determined that chocolate brings smile to any face and that is the key to becoming the most favorite Knight. So, Timothy has decided to send a chocolate bar to each and every UCF student. Specifically, Timothy will send a rectangular chocolate bar (made of smaller rectangular chocolate pieces assembled together) to as many UCF students as he can.

However, Timothy realizes that if two students see that they both received the same chocolate gifts, they would be repulsed and find this otherwise kind act suddenly creepy. To combat this, Timothy has decided that each gift he sends must be different. Thus, no pair of chocolate bars can have the same dimensions. But, because the smaller pieces have designs on them, a 5-by-3 chocolate bar is considered different than a 3-by-5 bar. Note, however, that a 5-by-5 (i.e., square) bar is the same as another 5-by-5 bar even though the smaller pieces have designs on them.

Timothy realized that he could of course send as many students unique chocolate bars as he wants because there are obviously an infinite number of sizes of chocolate bars he could make. However, because Timothy is no longer on the programming team, he is not that rich anymore! A chocolate bar with width a and height b will cost Timothy a*b and he has limited savings in his bank account. Thus, he can only afford a certain number of chocolate bars. More specifically, the total cost for the bars cannot exceed his savings. He thus needs your help to determine, given his limited budget, the maximum number of students he could send chocolate bars to such that no pair of students receive chocolate bars with the same dimensions.

In addition to all of this, Timothy must send the chocolate bars in nicely wrapped boxes, each bar in a separate box (i.e., not all bars in one box). But, all the boxes have the same size, i.e., there are not several boxes with varying sizes to choose from. Thus, every chocolate bar he makes must fit into one box. Furthermore, when putting a bar in a box, the bar cannot be rotated as this would cause the pattern on the chocolate to not match the pattern on the box. For example, let’s assume the box has width 3 and height 5, then a 3-by-5 bar would fit in the box but a 5-by-3 bar will not fit in the box (again, the bar cannot be rotated).

Given Timothy’s savings balance, determine the maximum number of rectangular chocolate bars he could make, such that no two bars have the same dimensions. Note that Timothy does not need to use up all of his money, but he cannot (of course) exceed his savings balance. Note also that each bar must fit into the given box size, i.e., the box size also restricts the bars he can make.

The input consists of a single line containing three positive integers, w, h, and x (1 ≤ w, h, x ≤ 10¹⁸) representing (respectively) the width and height of each box and Timothy’s savings balance.

Output a single line containing an integer representing the maximum number of students Timothy can send chocolate bars to given his constraints.