Алгоритмы

Сад Беси имеет \(N\) растений, помеченных от \(1\) до \(N\) (\(2\leq N\leq 5\cdot 10^5\)) слева направо. Беси знает, что растение \(i\) требует не менее \(w_i\) (\(0\leq w_i \leq 10^6\)) единиц воды.

У Беси своеобразная ирригационная система с \(N-1\) каналами, пронумерованными от \(1\) до \(N-1\). Каждый канал \(i\) имеет ассоциированную с ним стоимость \(c_i\) (\(1\le c_i\le 10^6\)), такую что Беси может заплатить \(c_i*k\) чтобы обеспечить растение \(i\) и \(i+1\) каждое \(k\) единицами воды где \(k\) неотрицательное целое число.

Беси сильно занята и может не иметь времени использовать все каналы. Для каждого \(2\leq i \leq N\) вычислите минимальную стоимость требуемую, чтобы доставить воду растениям от \(1\) до \(i\) используя только первые \(i-1\) каналов.

**Замечание: Время на тест в этой задаче 4 сек, в 2 раза больше, чем по умолчанию.**

Беси использует свой изящный телескоп чтобы сделать фотографии всех звёзд на ночном небе. Её телескоп может сделать фото \(N \times N\) (\(1 \leq N \leq 1000\)) пикселов, где каждый пиксел это или звезда, или пустое небо. Каждая звезда будет представлена ровно одним пикселом, и никакие две звезды на разделяют один и тот же пиксел.

Ночью происходит что-то странное со звёздами на небе. Каждая звезда или исчезает или перемещается на \(A\) пикселов вправо и на \(B\) пикселов вниз (\(0 \leq A,B \leq N\)). Если звезда исчезает или перемещается за границу фото, она больше не появляется на втором фото.

Беси делает фотографии до и после перемещений, но после экспериментов, она случайно наложила одну фотографию на другую. Теперь она видит белые пикселы, которые были пустыми на обеих фотографиях, серые пикселы, где звезда была ровно на одном фото и чёрные пикселы, где была звезда на обоих фотографиях. Беси также помнит, что на второй фотографии не появились новые звёзды, поэтому первая фотография содержит все звёзды ночного неба. Если не существует исходного положения звёзд, которое может произвести финальное фото, выведите \(-1\).

Беси помогает Эльзе играть со словами. Слова берутся из банка, содержащего \(M\) различных слов, ни одно слово не является префиксом другого.

Пока банк не пустой, Беси выбирает слово из банка, удаляет его из банка, читает его Эльзе по одному символу за раз слева направо. Задача Эльзы сказать Беси, как только она уникально определит слово, после чего Беси прекращает чтение.

Беси уже решила читать слова из словаря в порядке \(w_1,w_2,\dots,w_M\). Если Эльза ответит так быстро, как это возможно, сколько символов из каждого слова прочитает Беси?

Слова заданы в сжатом формате. Сначала мы определяем \(N+1\) (\(1\le N\le 10^6\)) различных слов и затем банк слов состоит из всех этих слов, ни одно из которых не является префиксом другого. Слова определяются следующим образом:

• Изначально, 0-ое слово - пустая строка.
• Затем для каждого each \(1\le i\le N\), \(i\)-ое слово будет равно \(p_i\)-ому слову плюс дополнительный символ в конце (\(0\le p_i<i\)). Символы выбираются так, что все \(N+1\) слов различны.

Фермер Джон выстроил \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) своих коров в ряд \(a\). \(i\)'-ая корова от начала ряда \(a\) помечена целым числом \(a_i\) (\(1 \leq a_i \leq N\)). Несколько коров могут быть помечены одним и тем же числом.

ФД конструирует ряд \(b\) следующим образом:

• Изначально массив \(b\) пустой.
• Пока массив \(a\) не пустой, удалить первый элемент ряда \(a\) и добавить или не добавить этот элемент в конец массива \(b\).

ФД хочет сконструировать \(b\) так, чтобы последовательность меток в \(b\) от начала к концу была лексикографически наибольшей.

Прежде чем ФД начнёт конструировать ряд \(b\), он может выполнить следующую операцию не более чем один раз.

• Выбрать корову в ряду \(a\) и переместить её в любую позицию, кроме текущей.

При условии, что ФД оптимально выполняет эту операцию не более одного раза, выведите лексикографически наибольшую последовательность \(b\), которую он сможет получить.

Каждый тест состоит из \(T\) (\(1 \leq T \leq 100\)) независимых подтестов.

**Замечание: Время на тест для этой задачи 3сек, в 1.5 большее чем по умолчанию. Память на тест для этой задачи 512MB, в два раза больше чем по умолчанию.**

Беси проходит тест вида да/нет из \(N\) вопросов (\(1\le N\le 2\cdot 10^5\)). За \(i\)-ый вопрос она может добавить \(a_i\) баллов если ответит правильно, и отнять \(b_i\) баллов, если ответит неправильно или не изменить сумму, если не ответит вообще на вопрос (\(0<a_i,b_i\le 10^9\)).

Беси знает ответы на все вопросы, но боится, что администратор теста Эльза подменит до \(k\) вопросов так, чтоб получилось, что Беси ответила неправильно.

Заданы \(Q\) (\(1\le Q\le N+1\)) кандидатов величин \(k\) (\(0\le k\le N\)), определите количество баллов, которые Беси гарантированы для каждого \(k\), зная, что она должна ответить не менее чем на \(k\) вопросов.

У Фермера Джона есть \(N\) коров, помеченных числами от \(1\) до \(N\) (\(2\le N\le 16\)). Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если между ними есть ребро в этом графе.

За одну операцию Вы можете добавить или удалить одно ребро в этом графе. Посчитайте минимальное количество операций, которое требуется выполнить, чтобы обеспечить следующее свойство в этом графе: Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\) по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).

У Фермера Джона есть квадратный холст, представленный решёткой из \(N\) * \(N\) ячеек, (\(2 \leq N \leq 2000\), \(N\) чётное). Он рисует по следующим правилам:

1. Сначала он делит холст на четыре равных квадранта, разделённых горизонтальными и вертикальными линиями через центр холста.
2. Далее он рисует любимую картинку в правом верхнем квадранте холста. Каждая ячейка верхнего правого квадранта или закрашена (представлено символом '#') или не закрашена (представлено символом '.').
3. Наконец, гордясь своим рисунком, он отражает его через ранее указанные вертикальные и горизонтальные линии в другие квадранты холста.

Например, предположим \(N=8\) и ФД нарисовал следующую картинку в правом верхнем квадранте на шаге 2:

.#..
.#..
.##.
....

Тогда после отображения через горизонтальные и вертикальные линии в другие квадранты на шаге 3, холст будет выглядеть так:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Однако, пока ФД спал, Беси пробралась в его амбар и украла холст. А затем занялась вандализмом: Она стерла некоторые ячейки и закрасила некоторые другие ячейки. После чего вернула холст ФД.

ФД хочет модифицировать холст так, чтобы он снова удовлетворял условиям отражения, то есть результату отражения правого верхнего квадранта во все остальные квадранты. Поскольку он имеет ограниченное количество ресурсов, он хочет получить результат минимальным количеством операций, закрашивания или стирания одной ячейки.

Вам задан холст после вандализма Беси, а также последовательность \(U\) (\(0\le U \leq 10^5\)) модификаций холста, каждое переключает ячейку в '.', если в ней была '#' и наоборот. Прежде каждого обновления и после каждого обновления выведите минимальное количество операций \(x\), которое требуется выполнить, чтобы отражение было удовлетворено.

ПР�МЕР ВВОДА:

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

ПР�МЕР ВЫВОДА:

4
3
2
1
0
1

Следующий холст удовлетворяет условию отражения и отличается от оригинального холста на 4 операции:

....
####
####
....

Невозможно сделать исходный холст удовлетворяющим условию отражения испольуя менее чем 4 операции.

После обновления \((1, 3)\), холст выглядит так:

....
##.#
####
..##

Требуется 3 операции, чтобы холст стал удовлетворять условию отражения.

После обновления \((2, 3)\), холст выглядит так:

....
####
####
..##

Требуется 2 операции, чтобы сделать холст удовлетворяющим условию отражения.

Автор: Chongtian Ma

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

Определение:

• программа это непустая последовательность операторов.
• Оператор имеет форму "PRINT \(c\)" где \(c\) - целое число, или "REP \(o\)", за которым следует программа, за которой следует "END", где \(o\) - целое число не менее 1.

• Выполнение программы исполняет операторы последовательности.
• Выполнение оператора "PRINT \(c\)" добавляет \(c\) в выходную последовательность.
• Выполнение оператора, начинающегося с "REP \(o\)" выполняет внутреннюю программу \(o\) раз

Пример программы Беси.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

Эта программа выведет последовательность \([1,2,2,1,2,2,1,2,2]\).

Беси хочет вывести последовательность \(N\) (\(1 \le N \le 100\)) положительных целых чисел. Эльза предложила Беси использовать не более \(K\) (\(1 \le K \le 3\)) операторов "PRINT". Заметим, что Беси может использовать сколько хочет операторов "REP". Также заметим, что каждое положительное число в последовательности не более \(K\).

Для каждого \(T\) (\(1 \le T \le 100\)) независимого подтеста определите, может ли Беси написать программу, которая выведет некоторую заданную последовательность, используя не более \(K\) операторов "PRINT".

Вам дан массив \(a\) из \(N\) неотрицательных чисел \(a_1, a_2, \dots, a_N\) (\(1\le N\le 2\cdot 10^5, 0\le a_i\le N\)). За одну операцию Вы можете изменить любой элемент \(a\) на любое неотрицательное число.

mex массива это минимальное неотрицательное число, которого нет в массиве. Для каждого \(i\) в интервале от \(0\) до \(N\) включительно, вычислите минимальное количество операций, которое Вы должны сделать, чтобы сделать mex массива \(a\) равным \(i\).

Беси ищет новую работу. К счастью сейчас \(K\) фермеров проводят интервью для найма работников. Поскольку желающих найти работу много, фермеры решили перенумеровать коров и интервьюировать их в порядке нумерации. \(N\) коров подали заявки на интервью, поэтому у Беси номер \(N+1\) (\(1 \leq K \leq N \leq 3 \cdot 10^5\)).

Процесс интервью проходит следующим образом. В момент времени \(0\) фермер \(i\) начинает интервью с коровой \(i\) для каждого \(1 \leq i \leq K\). После того, фермер заканчивает интервью он немедленно начинает интервьюировать следующую корову по порядку. Если несколько фермеров закончили интервью в одно и то же время, следующая корова может выбрать сама к какому из фермеров пойдёт на интервью.

Для каждого \(1\le i\le N\), Беси знает, что интервью коровы \(i\) займёт ровно \(t_i\) минут (\(1 \leq t_i \leq 10^9\)). Однако она не знает, какого фермера предпочтёт каждая корова.

Поскольку работа очень важна для Беси, она хочет хорошо подготовиться к интервью. Чтобы сделать это, она должна знать, когда она попадёт на интервью и к какому фермеру может потенциально попасть. Помогите найти эту информацию!

У Беси есть два массива длины \(N\) (\(1 \le N \le 500\)). \(i\)-ый элемент первого массива есть \(a_i\) (\(1 \le a_i \le 10^6\)). \(i\)-ый элемент второго массива есть \(b_i\) (\(1 \le b_i \le 10^6\)).

Беси хочет разделить два массива на не-пустые подмассивы так что будут выполняться следующие условия:

1. Каждый элемент принадлежит точно 1 подмассиву.
2. Оба массива разделены на одинаковое количество подмассивов - пусть \(k\). То есть, первый массив разделён ровно на \(k\) подмассивов. И второй массив также разделён ровно на \(k\) подмассивов.
3. Для всех \(1 \le i \le k\),, среднее \(i\)-го подмассива слева первого массива строго меньше либо равно среднему \(i\)-го подмассива слева второго массива.

Подсчитайте сколькими способами можно разделить массивы на непустые подмассивы выполнив указанные ограничения. Выводить ответ по модулю \(10^9+7\). Два способа считаются различными, если количество элементов подмассива различается или некоторый элемент принадлежит различным подмассивам.

Фермер Джон и его \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) коров на Манхеттене. Коровы сбежали и гуляют по городу. В Манхеттене \(N\) (\(1 \le N \le 2 \cdot 10^5\)) дорог проходящие бесконечно на \(x\)-\(y\)-плоскости. Все они расположены или горизонтально, или вертикально. Каждая горизонтальная или вертикальная может быть смоделирована уравнением вида \(y = c_i\) или \(x = c_i\), где \(c_i\) целое число в интервале от \(0\) до \(10^9\) включительно.

ФД знает точно где каждая корова начала путешествие и время путешествия. Каждая из коров движется по следующему шаблону:

• РћРЅР° двигается РЅР° север (\(+y\)) или восток (\(+x\)) РЅР° РѕРґРЅСѓ единицу РІ секунду.
• Если РѕРЅР° РЅР° одиночной РґРѕСЂРѕРіРµ, РѕРЅР° продолжает двигаться РїРѕ ней.
• Если РѕРЅР° РЅР° пересечении РґРІСѓС… РґРѕСЂРѕРі, РѕРЅР° идёт РЅР° север, РЅР° чётной секунде путешествия Рё РЅР° восток иначе.

ВАм дана карта Манхэттена и информация о каждой корове, помогите ФД где его коровы сейчас.

ПР�МЕР ВВОДА:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

ПР�МЕР ВЫВОДА:

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Автор: Benjamin Qi

Беси прыгает вдоль числовой прямой длины \(N\) \((1 \leq N \leq 10^5)\) по позициям \(1,2,\dots,N\) слева направо. Она начинает в позиции \(S\) \((1 \leq S \leq N)\) прыжком вправо со стартовой энергией \(1\). Если энергия Беси равна \(k\), то её следующий прыжок будет на \(k\) единиц вперёд от её текущей позиции.

Каждая целочисленная позиция от \(1\) до \(N\) это или цель, или прыжковая площадка. Каждая цель или прыжковая площадка имеет целочисленную величину от \(0\) до \(N\) включительно. Прыжковая площадка со значением \(v\) увеличивает энергию Беси на \(v\) и изменяет на противоположное направление прыжков. Цель со значением \(v\) будет сломана, если на неё приземлится Беси с энергией не менее \(v\). Приземление на цель не изменяет энергию и направление Беси. Сломанная цель остаётся сломанной, но Беси может на неё прыгать, энергия и направление не меняются.

Если Беси будет прыгать бесконечное количество времени или до тех пор, пока Беси покинет этот отрезок прямой, сколько целей она сломает?

Если Беси начинает на цели, которую она может сломать, она немедленно делает это. Аналогично, если Беси начинает на прыжковой площадке, то эффект площадки применяется перед первым прыжком.

У Фермера Джона \(N\) (\(1\le N\le 2\cdot 10^5\)) участков травы на прямой, где участок \(i\) имеет уровень бактерий, который отличается на \(a_i\) от здоровой травы (\(-10^{15}\le a_i \le 10^{15}\)). Например, если \(a_i = -3\), тогда кусок \(i\) имеет уровень бактерий на 3 меньше, чем нормальный. И нужно прибавить ровно 3 дополнительных единицы бактерий, чтобы уровень бактерий в этом куске рассматривался как нормальный.

ФД хочет обеспечить, чтобы каждый кусок травы был скорректирован, чтобы получить нормальные уровни бактерий на них. У него есть два вида пестицидов, один добавляет бактерии, другой удаляет бактерии. ФД распространяет любой из двух видов пестицидов, стоя в куске \(N\) (самом правом куске) и выбирает уровень мощности \(L\) (\(1 \leq L \leq N\)).

Сила действия спрейера уменьшается по мере увеличения расстояния от него. Например, если фермер выберет пестицид, который добавляет бактерии, тогда \(L\) единиц бактерий в участок \(N\), \(L-1\) единиц бактерий в участок \(N-1\), \(L-2\) единицы бактерий в участок \(N-2\) и т.д. Участки \(1 \ldots N-L\) не получат бактерий, поскольку мощность спрейера недостаточна, чтобы их достать. Аналогично, если ФД выберет пестициды, которые удаляют бактерии, тогда \(L\) единиц бактерий будет удалено с участка \(N\), \(L-1\) единиц бактерий будет удалено с участка \(N-1\) и т.д. Опять, участки \(1 \ldots N-L\) будут не изменены.

Определите минимальное количество раз, которое ФД должен применить свой спрейер так, чтобы на каждом участке стало рекомендованное количество бактерийю Гарантируется, что ответ не превысит \(10^9\).

Может потребоваться использование 64-битного типа данных (например "long long" в C/C++)

Беси занялась химией. В данный момент у неё есть жидкости двух различных цветов \(1\) и \(2\), которые плохо смешиваются одна с другой. У неё также есть две различных колбы бесконечной емкости наполненные \(N\) \((1 \leq N \leq 10^5)\) единицами смесей жидкостей этих двух цветов. Смеси делятся на слои отдельных цветов. Поэтому колбы можно рассматривать как строки \(f_1f_2\ldots f_N\) и \(s_1s_2\ldots s_N\) где \(f_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна первой колбы, \(s_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна второй колбы,

Беси хочет разделить эти жидкости так, чтобы каждая колба содержала все единицы жидкости одного цвета. У Беси есть также пустой стакан бесконечной емкости, чтобы помочь ей решить её задачу. Когда Беси делает одно переливание, она переливает всю жидкость цвета \(i\) наверх из одной колбы в другую или в стакан.

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

В каждом тесте будет \(T\) (\(1 \leq T \leq 10\)) подтестов с параметром \(P\) для каждого подтеста.

Предположим, что минимальное количество переливаний, чтобы разделить жидкости по колбам равно \(M\).

• если \(P=1\), Р’С‹ получите баллы, если выведите только \(M\).
• Если \(P=2\), Р’С‹ получите баллы, если выведите целое число \(A\) такое, что \(M \leq A \leq M+5\), Р·Р° которым следует \(A\) строк, которые конструируют это решение Р·Р° \(A\) С…РѕРґРѕРІ. Каждая строка должна содержать описание источника Рё приемника жидкости (\(1\), \(2\), или \(3\) для стакана). Колба-источник должна быть непустой перед переливанием, Рё нельзя переливать РІ себя.
• If \(P=3\), Р’С‹ получите баллы, если выведите \(M\), Р·Р° которым следует правильная конструкция, использующая это количество С…РѕРґРѕРІ.

ПР�МЕР ВВОДА:

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

ПР�МЕР ВЫВОДА:

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

Вот как это делается

1: 1221
2: 2211
3: 

1: 122
2: 22111
3: 

1: 1
2: 22111
3: 22

1: 1111
2: 22
3: 22

1: 1111
2: 2222
3:

В последнем подтесте пминимальное количество переливаний - \(5\). Однако, поскольку \(P=2\), то данная конструкция с \(6\)-ю ходами корректна, посокльку она не более чем на \(5\) переливаний от оптимального ответа.

Автор: Suhas Nagar

Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет \(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.

После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\) шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть. Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только \(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\) ходов прежде, чем Беси надоест, и она перестанет играть. Можете ли Вы определить лексикографически минимальную последовательность ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.

Беси готовит тесты для олимпиады. Каждую минуту она может выбрать не готовить никакие тесты для экономии энергии или потратить \(3^{a-1}\) энергии для подготовки \(a\) тестов для некоторого положительного целого \(a\).

У Фермера Джона есть \(D\) (\(1\le D\le 2\cdot 10^5\)) требований. Для \(i\)-го требования он говорит Беси, что в течение первых \(m_i\) минут она должна приготовить не менее чем \(b_i\) тестов (\(1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}\)).

Пусть \(e_i\) - минимальное количество энергии, которое необходимо Беси, чтобы удовлетворить первые \(i\) требований. Выведите \(e_1,\dots,e_D\) по модулю \(10^9+7\).

**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**

Беси планирует бесконечное путешествие в стране с \(N\) (\(1\leq N \leq 10^5\)) городами. В каждом городе есть портал и время зацикливания \(T_i\). Все \(T_i\). являются степенями двойки и \(T_1 + \cdots + T_N \leq 10^5\). Если Вы войдёте в портал города \(i\) в день \(t\), Вы немедленно выйдете из портала в городе \(c_{i, t\bmod{T_i}}\).

У Беси есть \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) планов её путешествия, каждый из которых есть тройка чисел \((v, t, \Delta)\). В каждом плане она начинает в городе \(v\) в день \(t\). Затем она делает следующее \(\Delta\) раз. Она входит в портал текущего города, затем ждёт один день. Для каждого из её планов она хочет узнать, в каком городе она закончит путешествие.

\(N\) \((1 \leq N \leq 5 \cdot 10^5)\) коров Фермера Джона выстроены в круг. \(i\)-ая корова имеет ведро с целой вместимостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально полные.

Каждую минуту корова \(i\) передаёт всё молоко из своего ведра корове \(i+1\) для \(1\le i<N\), а корова \(N\) передаёт своё молоко корове \(1\). Все обмены проходят одновременно (то есть, если корова отдаёт \(x\) литров молока и также получает \(x\) литров молока, её количество молока не изменяется). Если количество молока у коровы \(i\) превысит значение \(a_i\), тогда лишнее молоко теряется.

После каждой из минут \(1, 2, \dots, N\) - сколько молока останется у всех коров вместе?

\(N\) \((1 \leq N \leq 2 \cdot 10^5)\) коров Фермера Джона выстроены в круг так, что для каждой коровы \(i\) в промежутке \(1,2,\dots,N-1\), справа от коровы \(i\) расположена корова \(i+1\), а справа от коровы \(N\) находится корова \(1\). У каждой коровы имеется ведро целочисленной ёмкостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально заполнены молоком.

Каждую минуту коровы обменивается молоком по правилу, описанному в строке \(s_1s_2\dots s_N\) , состоящей только из символов \(\text{�L’}\) и \(\text{�R’}\). Если у коровы есть хотя бы \(1\) литр молока, она отдаст ровно \(1\) литр молока корове слева от неё, если \(s_i=\text{�L’}\), или справа от неё, если \(s_i=\text{�R’}\). Все обмены происходят одновременно (то есть, если у коровы полное ведро и она отдаёт литр молока и получает литр молока, то её молоко сохраняется). Если количество молока превысит \(a_i\), то лишнее молоко будет утеряно.

ФД хочет узнать после \(M\) минут \((1 \leq M \leq 10^9\)), какое количество молока останется у всех коров.?

ПР�МЕР ВВОДА:

3 1
RRL
1 1 1

ПР�МЕР ВЫВОДА:

2

ПР�МЕР ВВОДА:

5 20
LLLLL
3 3 2 3 3

ПР�МЕР ВЫВОДА:

14

ПР�МЕР ВВОДА:

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

ПР�МЕР ВЫВОДА:

38

Авторы: Chongtian Ma, Alex Liang