Maximizing Erzähler Operations

In this problem, you are given two series of items. The first series represents the leaves owned by Y, and the second series represents the snowflakes owned by Z. The value of the i-th leaf is defined as:

[ C_i = \begin{cases} x\times i & \text{if } x\times i \le K \ -K & \text{otherwise} \end{cases} ]

Similarly, the value of the i-th snowflake is:

[ E_i = \begin{cases} y\times i & \text{if } y\times i \le K \ -K & \text{otherwise} \end{cases} ]

An operation consists of selecting one leaf and one snowflake such that the sum of their values is at least (K) and then removing them from the collection. Note that each item can be used at most once. Your task is to determine the maximum number of operations that can be performed.

Input: Three positive integers (x), (y), and (K), provided in a single line separated by spaces.

Output: A single integer representing the maximum number of operations possible.

Hint: Notice that only the items with indices (i) such that (x\times i \le K) (and similarly for snowflakes) have positive values. Items with a value of (-K) will never help form a valid pair, so only consider the ones with positive computed values. A greedy pairing strategy using two pointers is likely to be optimal.

inputFormat

The input consists of a single line containing three integers separated by spaces:

(x) (y) (K)

where:

(1 \le x, y, K \le 10^9) (constraints are not strict but guarantee that the operations can be computed without overflow).

outputFormat

Output a single integer which is the maximum number of operations that can be performed by pairing one leaf with one snowflake such that their sum of values is at least (K).

sample

1 1 3

3