Одиннадцатиклассник Кирилл увлекается современными технологиями, в частности, загадочным разделом информатики «machine learning» (машинное обучение). Сейчас он собирается решать задачи на построение и обучение нейросетей.
Самая простая нейросеть представляется в виде n слоев нейронов. Первый — это «входной» слой, на который подаются параметры изучаемого объекта, n-ый — это «выходной» слой, итоговые значения в нейронах которого — реакция сети на объект (ответ). Остальные, промежуточные слои, пронумерованы от 2 до (n - 1) и призваны производить «мыслительный процесс». При этом для любого 1 ≤ i ≤ n - 1, каждый нейрон i-го слоя и каждый нейрон (i + 1)-го связаны.
Заметим, что в условиях нашей задачи сеть может не иметь промежуточных слоев, более того, входной слой может являться и выходным одновременно.
Кирилл хочет построить сеть мощности как минимум k. Он еще не очень разбирается в новой теме, но считает, что мощность нейросети — суммарное количество путей из вершин входного слоя в вершины выходного слоя. Мы будем считать только такие пути, которые включают в себя по одной вершине из каждого слоя.
Также Кирилл точно знает, что чем больше в сети нейронов, тем медленнее она обрабатывается, а значит, что из всех сетей мощности больше либо равной k он хочет построить ту, которая содержит минимальное количество нейронов.
Напишите программу, которая по количеству слоев и требуемой мощности поможет Кириллу найти минимальное необходимое число нейронов.
На вход даются 2 целых числа: n — количество слоев, и k — требуемая мощность нейросети (1 ≤ n ≤ 105, 0 ≤ k ≤ 1018).
Необходимо вывести одно число — минимальное необходимое число нейронов.
2 6
5
3 17
8
2 89
19
Заметим, что k может выходить за ограничения стандартных 4 байтовых типов языков программирования. Для работы с большими целыми числами в языке Pascal предусмотрен тип int64, а в C++ — тип long long.
Один из возможных вариантов сети для первого теста приведен на иллюстрации выше. Конфигурация сети: три входных вершины и две выходных, всего ровно 6 путей.
Возможная сеть для теста 2 изображена ниже. Также на рисунке выделен один из рассматриваемых путей. Заметим, что несмотря на наличие в данной сети целых 18 путей, невозможно составить сеть из меньшего количества вершин, удовлетворяющую условиям.
