Несмотря на то, что трамвай будет ехать с очень высокой скоростью, мэра беспокоит вид из окна трамвая, который откроется болельщикам и гостям города. Поэтому он решил, что нужно покрасить фасады домов, стоящих вдоль трамвайных путей.
Однако мэр никак не может определиться, в какой цвет он хотел бы покрасить фасады: ему одинаково симпатичны два цвета. Для определенности будем их называть первый цвет и второй цвет. Краска первого цвета поставляется в банках ёмкостью a литров, а краска второго цвета — в банках ёмкостью b литров.
Будем считать, что все n домов, фасады которых решено покрасить, расположены вдоль одной линии. Занумеруем их последовательно числами от 1 до n. Специальная измерительная комиссия уже выяснила, что для покраски фасада здания #j потребуется sj литров краски.
Впрочем, фирмы, занимающиеся покраской фасадов, заявили мэру и комиссии, что технологический процесс не позволяет использовать краску, оставшуюся после покраски одного дома, при покраске другого. Так что даже если из банки с краской был использован всего один литр, оставшуюся часть придётся утилизировать.
Это обстоятельство огорчило мэра. Поэтому он сформулировал следующие условия.
Во-первых, фасады домов с номерами от 1 до некоторого k (его и предстоит найти) должны быть покрашены в один из понравившихся мэру цветов (неважно, в какой именно), а фасады домов с номерами от k + 1 до n должны быть покрашены в другой из понравившихся ему цветов. При этом и в первый цвет, и во второй цвет должно быть покрашено хотя бы по одному фасаду.
Во-вторых, суммарное количество краски, которое придётся утилизировать ввиду особенностей технологического процесса, должно быть минимально возможным.
В-третьих, если существуют несколько вариантов покраски фасадов, удовлетворяющих первым двум условиям, мэр хочет, чтобы количество домов, фасады которых будут выкрашены в один цвет, отличалось от количества домов, фасады которых будут выкрашены в другой цвет, на минимально возможную величину.
Наконец, если и в этом случае существует более одного варианта покраски, мэр согласен на любой из них.
В первой строке содержатся целые числа n, a, b (2 ≤ n ≤ 3·105, 1 ≤ a, b ≤ 106) — количество домов, фасады которых нужно покрасить, ёмкость банки краски первого цвета, ёмкость банки краски второго цвета.
Во второй строке содержится n целых чисел s1, s2, ..., sn (1 ≤ sj ≤ 106, j = 1, 2, ..., n), где sj — количество литров краски, которое требуется для покраски фасада дома #j.
Выведите целые числа r, k и f.
Число r — минимально возможное количество краски, которое придётся утилизировать.
Числа k и f описывают план покраски.
Если f = 1, то фасады домов с #1 по #k следует покрасить в первый цвет, а фасады домов с #(k + 1) по #n — во второй цвет.
Если же f = 2, то фасады домов с #1 по #k следует покрасить во второй цвет, а фасады домов с #(k + 1) по #n — в первый цвет.
При выводе разделяйте числа пробелами или переводами строк.
10 5 3
11 7 2 4 9 8 10 13 19 14
11 6 2
10 2 3
17 21 4 2 14 12 11 23 9 3
4 5 1
5 1 2
3 6 8 2 5
1 2 2
Поясним приведённые примеры.
Рассмотрим первый пример.
Выпишем для каждого здания количество неизрасходованной краски при покраске его в первый цвет. Поскольку банка краски первого цвета имеет ёмкость 5, то остатки будут следующими:
Для второго цвета остатки будут такими:
Если первые 6 зданий будут покрашены во второй цвет, то неизрасходованной краски наберётся 7 литров (1 + 2 + 1 + 2 + 0 + 1). Здания с 7 по 10 будут покрашены в первый цвет, и неизрасходованной краски будет 4 литра (0 + 2 + 1 + 1).
Во втором примере, как можно заметить, здание #6 может быть покрашено в любой из двух цветов, и оставшейся краски при этом не будет.
Однако, поскольку мэр хочет, чтобы количество зданий, покрашенных в один цвет, отличалось от количества зданий, покрашенных в другой цвет, на минимально возможную величину, корректным ответом будет именно 4 5 1, а вывод 4 6 1 не будет считаться корректным ответом.
Третий пример иллюстрирует ситуацию, в которой выгоднее всего покрасить все здания в один цвет (в первый, поскольку банка краски этого цвета имеет ёмкость 1). Однако, поскольку существует требование покрасить в каждый из двух цветов хотя бы по одному зданию, минимально возможный расход краски будет составлять именно 1, а не 0.
Также заметим, что в третьем примере корректными ответами будут и 1 3 2, и 1 2 1, и 1 3 1.
Для чемпионата надо подготовить дорожки для катания, засеяв их газоном. Но погода не балует устроителей: то дождь, то град, то похолодание...
В распоряжении устроителей имеется n сортов травы, которые мы будем обозначать числами от 1 до n. Для каждого сорта #i известна минимальная температура bi, при которой эта трава не погибнет.
Синоптики города S подготовили долгосрочный прогноз погоды. Для каждого из m ближайших дней они рассчитали минимальную температуру, т.е. для дня #j определили значение tj.
Вырастить хороший газон совсем не просто. Дорожка имеет длину d единиц, но в течение дня можно посадить траву только на одной единице длины. Устроители обратились к ландшафтному дизайнеру, сообщив ему прогноз погоды и характеристики сортов травы, и попросили его составить план посадки. По мнению устроителей этот план должен был выглядеть как последовательность из d номеров сортов травы p1, p2, ..., pd. В первый день нужно будет посадить траву сорта p1, во второй — траву сорта p2 и т.д.
Пропускать дни при посадке устроители не хотят, так что если в некоторый день высадка газона будет начата, то она будет непрерывно продолжаться в течение d дней.
Разумеется, вся трава должна быть высажена до дня m включительно, и вся высаженная трава не должна погибнуть до дня m включительно.
Ландшафтный дизайнер составил план посадки травы и передал его устроителям. Но оказалось, что при записи плана дизайнер поступил следующим образом: если в течение нескольких дней подряд нужно было сажать траву одного и того же сорта, он указывал номер этого сорта только один раз.
Теперь перед устроителями стоит непростая задача. Во-первых, им нужно превратить «сжатый» план, который им передал дизайнер, в «развёрнутый», состоящий ровно из d номеров сортов травы. Во-вторых, устроителям нужно понять, в какой день следует начать реализовывать план посадки.
Так как может существовать и несколько способов превращения «сжатого» плана в «развёрнутый», и несколько допустимых для начала посадки дней, устроители хотели бы выбрать такой вариант «развёрнутого» плана, который они смогут начать реализовывать в наиболее ранний день.
Ваша задача — определить наиболее ранний день, подходящий для реализации плана.
В первой строке содержатся целые числа n, m, d (1 ≤ n ≤ 105, 1 ≤ d ≤ 105, d ≤ m ≤ 105) — количество сортов травы, количество дней, для которых сделан прогноз погоды, длина дорожки.
Во второй строке содержатся целые числа bi (i = 1, 2, ..., n, 0 ≤ b1 < b2 < ... < bn ≤ 106), где bi — минимальная температура, приемлемая для сорта травы #i.
В третьей строке содержатся целые числа tj (0 ≤ tj ≤ 106, j = 1, 2, ..., m), где tj — минимальная температура в день #j согласно прогнозу синоптиков.
В четвертой строке содержится целое число q (1 ≤ q ≤ d) — длина плана, который представил ландшафтный дизайнер.
В пятой строке содержится q целых чисел через пробел s1, s2, ..., sq (1 ≤ sk ≤ n, k = 1, 2, ..., q) — номера сортов травы в порядке их высадки.
Выведите минимально возможный номер дня, в который следует начать посадку согласно предложенному плану.
Если реализовать план невозможно, выведите - 1.
8 15 7
3 5 8 11 14 17 21 22
0 4 2 7 5 9 8 13 15 18 20 17 23 19 20
4
3 5 6 4
6
3 8 5
2 6 9
4 5 8 4 5 9 6 8
3
2 3 1
-1
Поясним приведённые примеры.
В первом случае «сжатый» план 3 5 6 4 ландшафтного дизайнера может быть «развёрнут» несколькими способами: например, как 3 5 5 5 6 4 4, или же как 3 3 5 6 4 4 4, или как 3 3 3 5 6 6 4. Несложно выяснить, что последний из вариантов «развёрнутого» плана можно начать реализовывать уже в день #6.
Во втором случае план реализовать не удастся.
Действительно, существует только один день, температура в который будет приемлемой для сорта травы #3 — это день #6. Однако проблема состоит в том, что даже если её высадить в этот день, в последующие два дня температура будет для неё ниже допустимой, и до истечения m дней эта трава погибнет.
Плохая погода мешает не только ответственным за газон. Бригада, которая осуществляет монтаж кресел на трибунах, тоже полагает, что при дожде и сильном ветре качество работы будет слишком низким, и поэтому в плохую погоду занимается тем, что ожидает хорошую погоду.
В некоторые дни на стадион привозят очередную партию кресел; а в некоторые дни приезжает инспектор, который проверяет качество выполненных работ, а также фиксирует, сколько всего кресел уже смонтировано. Кресла на стадион всегда привозят рано утром, а инспектор всегда приезжает в конце рабочего дня.
С начала монтажа кресел прошло n дней, а завтра рано утром проверять стадион приедет самый главный инспектор. По сведениям из надёжных источников, он полагает, что бригада много времени простаивает, и крайне недоволен этим. Он уже заинтересовался, какое максимальное количество кресел можно смонтировать в течение рабочего дня. Инженер, которого самый главный инспектор попросил дать ответ на этот вопрос, является хорошим товарищем бригадира и хочет ему помочь.
Инженер хочет назвать минимально возможное положительное количество кресел, которые можно смонтировать в течение рабочего дня, но так, чтобы это количество не противоречило известным данным. Как понятно, бригада не может монтировать ещё не привезённые кресла, а количество смонтированных кресел в конце дня очередной инспекторской проверки должно совпасть с количеством, зафиксированным инспектором.
Заметим, что бригада в какие-то дни может монтировать меньшее количество кресел, нежели то, которое назовет инженер. Также ещё раз обратим ваше внимание, что в день приезда самого главного инспектора никакие работы не планируются.
Ваша задача — определить, какое число следует назвать инженеру.
В первой строке содержится целые числа n и m (1 ≤ n ≤ 105, 1 ≤ m ≤ 2·n) — количество дней работы бригады и количество записей о доставке кресел и приезде инспекторов.
Запись #j о доставке кресел или о приезде инспектора состоит из трёх чисел — dj, tj, cj 
, где dj — номер дня, в который сделана запись, tj = 1 означает, что в этот день на стадион привозили кресла, а tj = 2 — что в этот день на стадион приезжал инспектор. Если tj = 1, то 1 ≤ cj ≤ 104.
Гарантируется, что все входные данные корректны.
Гарантируется, что для каждого дня существует не более одной записи о доставке кресел и не более одной записи о визите инспектора.
Гарантируется, что записи следуют в хронологическом порядке, т.е. d1 ≤ d2 ≤ ... ≤ dm. Если для одного и того же дня есть и запись о доставке кресел, и запись о приезде инспектора, они присутствуют именно в таком порядке.
Также гарантируется, что все значения cj при tj = 2 образуют корректную неубывающую последовательность, а для каждого cj при tj = 2 верно, что 
.
Во второй строке входного файла содержатся величины d1, d2, ..., dm, в третьей строке — величины t1, t2, ..., tm, в четвёртой строке — величины c1, c2, ..., cm.
Выведите положительное целое число p — количество кресел, которое следует назвать инженеру.
10 7
2 4 5 5 7 8 8
1 2 1 2 1 1 2
11 8 1 9 3 7 14
3
Поясним приведённый пример.
Как можно видеть, кресла привозили во 2, 5, 7 и 8 день. Инспектора посещали стадион в 4, 5 и 8 день.
Можно удостовериться, что если в течение дня бригада могла смонтировать не более 3 кресел, то и данные о привозе кресел, и данные о приезде инспекторов являются корректными. Например, монтаж кресел мог выполняться следующим образом:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 0 | 3 | 2 | 3 | 1 | 0 | 3 | 2 | 3 | 2 |
Действительно, в первый день бригада не монтировала кресел, и это вполне понятно, поскольку кресел на стадион ещё не привозили.
Во второй день было доставлено 11 кресел; бригада смонтировала 3 кресла (условие не больше 3 соблюдено); в третий — 2 кресла, в четвёртый — снова 3 кресла. Суммарно это 8 кресел, что не превосходит количества кресел, которые в принципе могли быть смонтированы к этому дню, а также совпадает с данными инспектора, приезжавшего в четвёртый день.
Далее, в пятый день привезли одно кресло, и не смонтированных кресел стало 4 (3 осталось от предыдущей партии). Бригада в этот день смонтировала только одно кресло. Вечером инспектор насчитал 9 смонтированных кресел, а в распоряжении бригады осталось 3 пригодных для монтажа кресла.
В шестой день бригада не монтировала кресла. В седьмой день было доставлено ещё 3 кресла, а бригада смонтировала 3 кресла. Поэтому к вечеру седьмого дня имелось ещё 3 кресла, которые можно было монтировать.
Впрочем, утром восьмого дня привезли ещё 7 кресел (и суммарно их стало 10), а в течение восьмого дня бригада смонтировала 2 кресла. Суммарно к концу восьмого дня получается 14 кресел, что совпадает с подсчётами инспектора, посетившего стадион вечером этого дня.
Несмонтированными остались 8 кресел. В девятый день бригада могла бы смонтировать 3 кресла, в десятый день — два кресла (могли быть и другие значения, ибо до посещения самого главного инспектора никто об этом не узнает).
Также несложно убедиться, что 2 не может быть ответом. Если считать, что в день можно смонтировать не более 2 кресел, то получить 8 смонтированных кресел в четвёртый день (первое посещение инспектора) бригада никак не могла. Впервые кресла завезли только во второй день, и даже если бы каждый день бригада монтировала по 2 кресла, то к концу четвёртого дня смонтированных кресел было бы только 6.
Поскольку погода устроителей так и продолжает не радовать, они планируют использовать рулонный газон.
Дорожка для забега на роликах имеет длину n метров. Устроители очень тщательно готовятся к чемпионату, поэтому они поделили её на участки длиной 1 метр и для каждого такого участка провели исследование почвы. Оказалось, что придётся использовать два вида газона. Для определённости будем называть их A и B.
Компания, которая будет выполнять работы, укладывает один метр газона вида A за p1 денежных единиц, а один метр газона вида B за p2 денежных единиц. Однако если заказать укладку d1 или более метров газона вида A подряд, то один метр обойдётся немного дешевле: s1 денежных единиц. Для газона вида B тоже есть оптовая скидка: если заказать укладку d2 или более метров этого газона подряд, то один метр будет стоить s2 денежных единиц.
Устроители располагают картой дорожки для забега, на которой каждый участок помечен символом A, если на нём допустимо использовать только газон вида A, символом B, если допустимо использовать только газон вида B, и символом 0, если можно использовать как газон вида A, так и газон вида B.
Ваша задача — определить минимальную стоимость работ по покрытию дорожки газоном.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — длина дорожки для забега.
Во второй строке содержится n символов A (заглавная латинская буква), B (заглавная латинская буква), 0 (ноль), означающих, какой вид газона можно использовать для данного участка.
В третьей строке содержатся целые числа p1, d1, s1 (1 ≤ s1 < p1 ≤ 105, 2 ≤ d1 ≤ 105), описанные в условии задачи.
В четвёртой строке содержатся целые числа p2, d2, s2 (1 ≤ s2 < p2 ≤ 105, 2 ≤ d2 ≤ 105), описанные в условии задачи.
В первой строке выведите минимально возможную стоимость покрытия дорожки газоном.
Во второй строке выведите карту дорожки, в которой символы 0 заменены на символы A или B в зависимости от выбора типа газона.
10
AB000A00B0
5 3 2
3 4 1
18
ABBBBABBBB
6
0A0BA0
5 3 2
3 4 1
17
AAABAB