Скільки точок перетину?#1539

Скільки точок перетину?

1 секунда
128 мегабайтів
Середня

У нас є два ряди точок. У верхньому ряду розташовано точок, у нижньому — точок. Кожна точка верхнього ряду з'єднана відрізком з кожною точкою нижнього ряду. Точки розташовано так, щоб кількість внутрішніх точок перетину відрізків була максимальною. Для досягнення цього не повинно бути жодної точки, в якій перетинаються три відрізки. Точки перетину, які знаходяться безпосередньо на самих рядах, не враховуються; будь-яка кількість відрізків може перетинатися у цих точках. Задано числа і , обчисліть P(a, b) — максимальну кількість точок перетину між двома рядами. Наприклад, коли a = 2 та b = 3, як показано на рисунку, то P(2, 3) = 3.

prb1539

Вхідні дані

У кожному рядку задано два натуральні числа (0 < a \leq 20000) та (0 < b \leq 20000). Останній тест містить два нуля і не повинен оброблятися. Всього не більше тестів.

Вихідні дані

Для кожного тесту виведіть його порядковий номер та значення P(a, b) в окремому рядку.Результат вміщується у 64-бітне ціле зі знаком.

Приклади

Приклад 1

Loading
Loading