Selecting Top Students Without Protest

The teacher wants to select m top students from n students. However, there are k pairs of students whose abilities are equal. In order to avoid protests, if two students form a pair then either both must be selected or both must be left out. In other words, students forming an equal‐ability pair cannot be split between the selected and non-selected group. The teacher now wonders: what is the number of top students he should actually select so that (1) no pair is split, and (2) the number selected is as close as possible to the original m?

Formally, if a pair is selected then both students contribute 2 to the total count. Let the number of pairs chosen be c (with 0 ≤ c ≤ k) and let the number of "single" students (i.e. those not belonging to any pair) chosen be s (with 0 ≤ s ≤ n-2k). Then the total number selected is

\( x = 2c + s \)

The valid selection counts are those values of x obtainable in this way. Note that if there is at least one single student (i.e. if n - 2k > 0), then every integer from 0 to n is achievable. However, if n - 2k = 0 (i.e. every student is in a pair) then only even numbers are possible. In such a case if m is even one may select m students, but if m is odd then the two nearest possible counts are m-1 and m+1. In this problem, if there is a tie in absolute difference, choose the larger number.

Your task is to compute the number of top students to select according to the criteria above.

inputFormat

The input consists of a single line containing three positive integers n, m, and k separated by spaces, where:

• n is the total number of students,
• m is the desired number of students to select, and
• k is the number of pairs of students with equal ability.

You may assume that m ≤ n and that the k pairs are disjoint (i.e. they involve 2k distinct students).

outputFormat

Output a single integer, the number of students to select, which satisfies the constraint that in each equal‐ability pair either both students are selected or none, and which is as close as possible to m. In case of a tie, output the larger number.

sample

10 3 2

3