Задача C. Небоскреб ≡

Условие

Артем и Женя обожают строить здания из кубиков. Они уже строили из них гаражи, домики и даже средневековые замки... Сегодня ребята решили возвести небоскреб. У Артема есть n синих кубиков, а у Евгения m красных. По мысли ребят, построенный небоскреб должен представлять собой два прямоугольных параллелепипеда с квадратными основаниями разного размера, установленные один на другой. Мальчики хотят, чтобы каждый из них построил свою часть многоэтажного строения исключительно из всех своих кубиков, а потом установить один параллелепипед на другой.

Естественно, мальчики хотят порадовать своих родителей и сделать небоскреб как можно выше. Проблема не была бы столь серьезной, если бы они строили на открытом воздухе. Но на улице сильный дождь, а дома невозможно построить небоскреб выше k кубиков. Помогите ребятам рассчитать наибольшую высоту небоскреба, которой они могут достичь.

Формат входных данных

Первая строка входного файла содержит три натуральных числа, записанных через пробел: n, m и k.

Формат выходных данных

Выведите одно неотрицательное целое число — наибольшую высоту построенного небоскреба.

Ограничения

1 ≤ n, m, k ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере у Артема 729 кубиков, а у Жени 1024. Наибольшая высота небоскреба, который может быть построен дома, не может превышать 15. Ребята действуют так: сначала Евгений строит из своих кубиков основание небоскреба в виде прямоугольного параллелепипеда: 16 × 16 × 4 (обратите внимание — основание параллелепипеда обязательно должно быть квадратным). Потом Артем устанавливает сверху на постройку Жени свой прямоугольный параллелепипед: 9 × 9 × 9, и высота небоскреба становится равна 13. Большей высоты с учетом всех ограничений достичь нельзя.

Во втором примере у ребят не получится составить небоскреб. Артем может построить свою часть в виде единственно возможного прямоугольного параллелепипеда: 1 × 1 × 17, Женя (аналогично): 1 × 1 × 19. Но, во-первых, обе построенные ими части будут иметь равное основание, а во вторых, общая высота небоскреба 36 превышает высоту помещения.

Примеры тестов

729 1024 15

13

17 19 30

0