Background

One morning, a little girl was playing in the forest when she saw a magical seed. It shone brightly and gave off a faint fragrance. The girl liked the seed very much, so she held it in her hands and brought it home.

That night, the girl had a dream and saw a kind-looking old man with a white beard. He told her that the seed in her hand came from a Moon Tree. Normally, it could only be seen on the Moon, but by chance, the seed quietly fell to Earth and could no longer return to the Moon.

The old man noticed that the girl liked the seed very much, so he asked whether she would be willing to rely on her hard work and wisdom to use this tiny seed to grow a dense Moonlight Forest, giving the Moon Trees a warm new home on Earth. The girl nodded excitedly and quickly asked what she should do exactly.

Problem Description

The old man explained that this seed was extraordinary. On the morning of the second day after planting, it would grow into a small sapling of height $1$ (one unit).

The Moon Tree is extremely resilient, and after that it will grow by one unit every morning. Since Moon Trees are different from organisms on Earth, the girl must use a special fertilizer to fertilize them, and the old man will give the girl one unit of this fertilizer every day. Every night, she must fertilize exactly one tree or a seed that was just planted in the afternoon. She cannot fertilize more, and she cannot skip fertilizing. The fertilized tree or seed will grow one extra unit the next morning compared to the normal case, i.e. it will grow by two units.

During the growth of a Moon Tree, there are two special heights called “harvest points”, which are $\text{HP1}$ and $\text{HP2}$. At noon on the day when the height of a Moon Tree first reaches or exceeds $\text{HP1}$, the tree will bear one fruit. Similarly, at noon on the day when its height first reaches or exceeds $\text{HP2}$, it will bear one fruit.

Inside each fruit there is one seed, exactly the same as the one the girl first found. Every afternoon, the girl may choose to plant some seeds, and of course she may also choose to plant none. Only when the girl has planted exactly $M$ trees and all of them have the same height can these trees truly adapt to Earth’s environment and live forever.

On the afternoon after she woke up, the girl planted the seed as the old man instructed. She took completing the task the old man gave her as the greatest wish of her life, working hard day after day and year after year. Every evening, as soon as she sat on the doorstep and looked into the distance, a beautiful and vast Moonlight Forest would appear before her eyes. She believed she would succeed, no matter how long it took. But when would that day finally come?

Input Format

Three integers $\text{HP1,\,HP2},\,M$, representing the heights of the two harvest points and the required number of Moon Trees.

Output Format

A single integer $T$, the minimum number of days required.

4 9 3

12

10 15 6

84

Hint

For $100\%$ of the testdata, $2 \leq \text{HP1,\,HP2} \leq 20$, $2 \leq M \leq 100$.

Translated by ChatGPT 5