Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

greedy

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Frodo and pillows

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard output*n* hobbits are planning to spend the night at Frodo's house. Frodo has *n* beds standing in a row and *m* pillows (*n* ≤ *m*). Each hobbit needs a bed and at least one pillow to sleep, however, everyone wants as many pillows as possible. Of course, it's not always possible to share pillows equally, but any hobbit gets hurt if he has at least two pillows less than some of his neighbors have.

Frodo will sleep on the *k*-th bed in the row. What is the maximum number of pillows he can have so that every hobbit has at least one pillow, every pillow is given to some hobbit and no one is hurt?

Input

The only line contain three integers *n*, *m* and *k* (1 ≤ *n* ≤ *m* ≤ 10^{9}, 1 ≤ *k* ≤ *n*) — the number of hobbits, the number of pillows and the number of Frodo's bed.

Output

Print single integer — the maximum number of pillows Frodo can have so that no one is hurt.

Examples

Input

4 6 2

Output

2

Input

3 10 3

Output

4

Input

3 6 1

Output

3

Note

In the first example Frodo can have at most two pillows. In this case, he can give two pillows to the hobbit on the first bed, and one pillow to each of the hobbits on the third and the fourth beds.

In the second example Frodo can take at most four pillows, giving three pillows to each of the others.

In the third example Frodo can take three pillows, giving two pillows to the hobbit in the middle and one pillow to the hobbit on the third bed.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/22/2024 19:32:53 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|