409192: GYM103455 B Prize Change
Description
After the Squid Game finishes, the prize money must be distributed!
To make the prize seem more massive, the organizers of the game have decided to only use bills worth one thousand won and two thousand won to give out the prize. However, the bank has capped the amount of each bill available and there are only $$$n$$$ bills worth one thousand won and $$$m$$$ bills each worth two thousand won available.
Given the amount of one thousand won and two thousand won bills available, find the number of distinct ways that the organizers can distribute exactly $$$k$$$ thousand won overall as the prize. Two ways to distribute won are distinct if they use a different number of one thousand won or two thousand won bills.
InputThe first line consists of three integers $$$n$$$, $$$m$$$, and $$$k$$$ $$$(1 \leq n, m, k \leq 10^6)$$$ giving the number of one thousand won bills, two thousand won bills, and the number of one thousand won bills needed to make the prize amount, respectively.
OutputOutput the number of distinct ways to give out exactly $$$k$$$ thousand won using only the $$$n$$$ one thousand won bills and the $$$m$$$ two thousand won wills.
ExampleInput30 20 60Output
6