Задача G. Подручные средства

Задачу добавил: alef

Успешно сдано решений: 92

Ограничения: время на тест - 2с, память - 256 Мб

Василий попросился пойти на фабрику вместе с Ли Си Цином. Пока они шли по заросшему плющом огромному зданию, Василий еле успевал разглядывать больших красивых птиц, которые явно облюбовали это место для гнездовий. Мастерская когда-то была комнатой с прозрачными стенами, но, чтобы укрыть ее от посторонних глаз, Ли Си Цин приладил с внешней стороны какой-то твердый отражающий материал.
- Ох, любопытные, - вздохнул отшельник. - Опять поправлять придется. Поможешь?
- Конечно! - с готовностью отозвался Василий. - А что нужно делать?
- Обшивку они все оторвать пытаются. И всегда именно в этом месте. То ли просто клювы точат, то ли что-то им здесь нравится...

Ли Си Цин объяснил Василию, что обшивка крепится в разных местах гвоздями и шурупами. Гвоздями - если под ней специальная рейка, а шурупами - там, где пришлось аккуратно фиксировать ее на стене. Шурупы он аккуратно закрутит сам, если будет такая необходимость. А вот гвозди надо просто забить обратно, что он и просит сделать Василия. Забивать можно молотком - по одному гвоздю, но можно и микроскопом - их тут много валяется, разного размера. В зависимости от размера микроскопом можно забить одновременно несколько подряд расположенных гвоздей. Только вот попадать по шурупам нельзя ни в коем случае - можно разбить стенку.

Все гвозди и шурупы (суммарно N штук) расположены вдоль прямой на равном расстоянии друг от друга. В распоряжении Василия имеется один молоток, одним ударом которого можно забить один гвоздь, и M микроскопов, для каждого из которых известно, сколько подряд идущих гвоздей можно им забить.

Василий хочет забить все гвозди как можно меньшим количеством ударов, соблюдая при этом требование Ли Си Цина не попадать по шурупам. Ваша задача - определить, сколько ударов ему понадобится.

Формат входного файла input.txt
Первая строка - целые числа N (1 <= N <= 2*10^6) и M (1 <= M <= 2*10^5) через пробел - количество гвоздей и шурупов и количество микроскопов.
Вторая строка - целые числа P1, P2, ..., PM - количество гвоздей, которые можно забить соответствующим микроскопом (все числа не менее 1 и не более 2*10^6).
Третья строка - N символов 'O' и 'X' (латинские буквы), где 'O' обозначает гвоздь, а 'X' - шуруп.
Гарантируется, что размер входного файла не превышает 4Мб

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

Пример входного файла - 1
14 2
3 5
OOXOOOOOOOXOOO

Пример выходного файла - 1
5

Пример входного файла - 2
10 10
13 14 7 4 10 15 19 11 16 3
OOOOOXOOOO

Пример выходного файла - 2
3

Сдать задачу

Задать вопрос жюри по этой задаче