Аня обожает собак, в особенности породу «Мальтипу». Она давно мечтала завести себе побольше этих прекрасных пёсиков, и вот наконец она решилась и осуществила давнее желание. Она завела себе сразу $$$N$$$ питомцев. Аня, как никто другой, знает, что кормить собачек можно только определённым кормом, в одной пачке которого содержится $$$W$$$ грамм лакомства. Также она знает, что для того чтобы наесться, каждой особи необходимо съесть не менее $$$C$$$ грамм корма. Теперь Аня хочет узнать, какое минимальное количество пачек корма ей надо купить, чтобы накормить своих питомцев.

В задаче используется оценка по подгруппам. Баллы за группу даются, только если все тесты этой группы успешно пройдены. Группа тестируется, только если пройдены все зависимые группы.

Город Екатеринбург в 2067 году развился до невероятных пределов: в городе появилась парковка! Еще и не простая, а прямоугольная. В ней есть $$$A$$$ рядов паркомест и $$$A$$$ мест в ряду. Но однажды большая богатая семья устроила свадьбу! Поэтому пришлось перекрыть центр города и свезти туда кучу розовых лимузинов. Причем лимузины не стандартные! Первый из них длиной как $$$1$$$ стандартная машина, второй как $$$2$$$ машины и так далее, самый большой длиной как $$$K$$$ стандартных машин. И их всех пришлось поставить на эту самую парковку, так как больше девать некуда. Начальство УралПаркинга просит вас посчитать, сколько мест останется на парковке, если поставить туда эти лимузины, и возможно ли это вообще.

Пример парковки $$$5 \times 5$$$. Лимузины (розовые) длиной $$$3$$$ и $$$2$$$. Каждый лимузин занимает непрерывную полосу клеток строго по горизонтали или вертикали. Свободные места отмечены серыми точками.

Поворачивать лимузины (располагать их под углом) запрещено.

В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены.

Лютик решил развлечь гостей таверны игрой в дартс. На мишени есть три области, приносящие $$$5$$$, $$$3$$$ и $$$1$$$ очко соответственно.

Бард хочет совершить ровно $$$k$$$ бросков и набрать в сумме ровно $$$x$$$ очков. При этом он поставил себе условие: попасть в первую область ($$$5$$$ очков) можно не более $$$n$$$ раз. Гарантируется, что каждым броском Лютик обязательно попадает в одну из трёх областей, и он может намеренно попасть в любую из них.

Если существует несколько способов достичь цели, он выбирает тот, в котором минимизируется количество попаданий в первую область ($$$5$$$ очков). Если же при минимальном количестве попаданий в первую область всё ещё есть несколько вариантов, он выбирает тот, в котором минимизируется количество попаданий во вторую область ($$$3$$$ очка).

Помогите Лютику определить, возможен ли такой расклад, и, если да, выведите количество попаданий в каждую из областей.

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

Дима ходит в зал, и его любимое упражнение — жим лёжа. У Димы есть план тренировок, согласно которому он должен сделать $$$n$$$ подходов с весами $$$a_1, a_2, \dots, a_n$$$.

В зале есть блины массами: $$$2.5, 5, 10, 20, 40$$$ кг.

Будем считать, что сама штанга волшебная и ее масса равна $$$0$$$.

Чтобы получить на штанге вес $$$A$$$, надо повесить с каждой стороны штанги блины с суммарным весом $$$\frac{A}{2}$$$ кг.

При этом с каждой стороны наборы блинов должны быть:

• одинаковыми,
• образовывать неубывающую последовательность,
• количество блинов на штанге должно быть минимально возможным.

Более формально: Дима хочет подобрать такой вес на штанге, чтобы среди всех наборов блинов, которыми это можно сделать, не существовало набора с меньшим количеством блинов и таким же суммарным весом.

Если Дима хочет получить на штанге вес $$$60$$$ кг, то на каждой стороне нужно набрать: $$$\frac{60}{2} = 30 $$$кг.

Из доступных блинов $$$2.5, 5, 10, 20, 40$$$ это можно сделать, например:

• $$$20 + 10$$$ — 2 блина,
• $$$10 + 10 + 10$$$ — 3 блина,
• $$$20 + 5 + 5$$$ — 3 блина.

Подходы выполняются в указанном порядке $$$a_1, a_2, \dots, a_n$$$.

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

Найти минимальную суммарную работу (число снятий $$$+$$$ число надеваний) или определить, что план тренировки невыполним.

В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены.

В столице Берляндии построили метро. Изначально была только одна центральная станция номер 1, а затем сеть разрасталась: добавлялись новые станции и перегоны. Время проезда по любому перегону составляет ровно 1 минуту, и движение возможно в обе стороны. Станции пронумерованы от 1 до $$$n$$$, где станция 1 — центральная.

Позднее из-за экономического кризиса пришлось закрыть множество перегонов, оставив ровно $$$n-1$$$ перегон так, чтобы от центра по-прежнему можно было добраться до любой станции. Сейчас экономика Берляндии снова на подъёме, и мэр решил построить ровно один новый перегон между какими-то двумя станциями, чтобы улучшить транспортную доступность.

Новый перегон должен быть построен так, чтобы суммарное время поездки от центра до всех станций стало минимальным. Формально, нужно минимизировать сумму $$$\text{dist}(1, i)$$$ по всем $$$i$$$ от $$$1$$$ до $$$n$$$, где $$$\text{dist}(a, b)$$$ — минимальное время в минутах, необходимое, чтобы добраться от станции $$$a$$$ до станции $$$b$$$ по существующим и новому перегону.

Помогите мэру Берляндии найти это минимальное возможное значение суммы.

В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены. Обозначим $$$p_i$$$ ближайшую станцию на пути до центра от станции $$$i$$$.