Вы когда-нибудь мечтали стать главным героем компьютерной игры? Главный герой этой истории, Бранимир, мечтает сейчас именно об этом.

Мир в мечте Бранимира состоит из N небоскребов, пронумерованных слева направо. Для i -го небоскреба, известна его высота H _i и количество золотых монет G _i на крыше этого небоскреба. Игра начинается с прыжка на любой из небоскребов и состоит из нескольких ходов. На каждом ходу Бранимир может прыгнуть на любой небоскрёб, находящийся справа от него, но так, чтобы высота нового небоскрёба была не меньше того небоскрёба, на котором сейчас сидит Бранимир. Оказавшись на крыше небоскреба, Бранимир собирает все золотые монеты на ней. Бранимир может закончить игру после любого количества шагов (возможно, нулевого), но он должен собрать не менее K золотых монет, чтобы перейти на следующий уровень.

Бранимир хочет узнать, сколько существует способов сыграть в эту игру так, чтобы перейти на следующий уровень. Две игры называются разными, если существует небоскреб который был посещен в одной игре, но не был посещён в другой.

Петя увлёкся алгоритмами сжатия данных. Он уже изучил форматы gz , bz , zip и несколько других. Воодушевившись новыми знаниями, Петя собрался разработать свой формат сжатия и назвать его dis .

Петя решил сжимать таблицы. У него есть таблица, состоящая из n строк и m столбцов, заполненная целыми положительными числами. Он хочет заменить значения элементов таблицы на целые положительные числа так, чтобы отношение элементов в каждой строке и каждом столбце не изменилось. То есть, если в некоторой строке исходной таблицы a _{i , j} < a _{i , k} , то и в сжатой таблице a ' _{i , j} < a ' _{i , k} , и если a _{i , j} = a _{i , k} , то a ' _{i , j} = a ' _{i , k} . Аналогично, если в некотором столбце исходной таблицы a _{i , j} < a _{p , j} , то и в сжатой таблице a ' _{i , j} < a ' _{p , j} , и если a _{i , j} = a _{p , j} , то a ' _{i , j} = a ' _{p , j} .

Поскольку б'{о}льшие значения требуют больше места для хранения, максимальное значение элемента получившейся матрицы должно быть как можно меньше.

В теории Петя мастер, но вот писать код он не любит. Помогите ему реализовать формат сжатия dis .

Вы знаете, в чём разница между отелем и мотелем? Верно, разница в количестве мух, которые там живут. Норман – владелец одного из самых популярных мотелей в Америке,но его мать хочет, чтобы он стал отелем. Именно поэтому Норман купил мухобойку ( мухобойка – инструмент для отпугивания или прихлопывания мух. Может представлять собой как пластиковое или резиновое изделие на длинной ручке, так и пучок волос или листьев). Мухобойка представляет из себя многоугольник из \(\)\(K\)\(\) рёбер.

Желая угодить своей матери, Норман встал у окна, на котором сидели \(\)\(N\)\(\) мух. Так как норманн – пацифист, он не может причинить вред другому живому существу, в том числе, мухе. Именно поэтому ему интересно количество способов ударить по окну мухобойкой, не задев ни одной мухи.

Окно представляет из собой прямоугольник с левой нижней вершиной в точке \(\)\((0, 0)\)\(\) и правой верхней – в точке \(\)\((X_p, Y_p)\)\(\). После того как Норман ударит по окну все вершины многоугольника должны лежать в точках с целыми координатами, а мухобойка должна полностью лежать внутри прямоугольника окна. Норману интересно, сколькими способами он может ударить по окну, не убив ни единой мухи.

Теперь вас назначили управляющим одной телекоммуникационной компании. Вы отвечаете за обеспечение маленького городка контентом. Каждый дом задается его координатами на плоскости. Известно, что никакие три дома не лежат на одной прямой, а никакие четыре на одной окружности. Вы решили поставить одну антенну так, чтобы сигнал от нее был доступен домам в определенным радиусе, т.е. область, в которой доступен контент является кругом. Вы еще не очень разобрались в политике вашей компании, поэтому решили сделать не слишком сложный выбор данной области: вы просто выбираете 3 случайных дома и строите круг так, чтобы эти три дома были на его границе (вы ходили на геометрию в 7 классе и вам известно, что так всегда можно сделать). Теперь вам интересно, сколько в среднем домов будут иметь доступ к контенту. Выведите ответ с точностью до 4 знаков после запятой.