Remote Training on Programming

Фермер Питер огородил свое новое пастбище отличным забором, состоящим из n досок. Забор имеет форму замкнутой ломаной. К сожалению, некоторые из этих досок покрашены в белый цвет, а некоторые — нет. Разумеется, фермер хочет, чтобы его пастбище было огорожено красивым забором, поэтому он решил покрасить весь забор в белый цвет.

Для покраски фермеру порекомендовали нанять компанию «В&М», расположенную в соседнем поселке. Он обратился в эту компанию, и ему предложили сделать заказ на покраску участков забора. Каждый заказ должен быть сформирован из множества предложений компании. Каждое предложение характеризуется количеством окрашиваемых досок a_i и стоимостью соответствующей работы c_i, и заключается в том, что за сумму c_i рублей сотрудники компании покрасят любые a_i идущих подряд досок в белый цвет.

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

Требуется написать программу, с помощью которой можно определить, какую минимальную сумму фермер Питер заплатит компании «В&М» за то, что весь его забор будет выкрашен в белый цвет.

Формат входных данных

Первая строка входного файла содержит два числа: n — количество досок в заборе (1 ≤ n ≤ 1000) и m — количество возможных предложений компании (1 ≤ m ≤ 40). Вторая строка содержит n символов, описывающих состояние покраски забора, где символ «+» означает уже окрашенную в белый цвет доску, а символ «0» — неокрашенную.

Последующие m строк содержат возможные предложения компании «В&М», где каждое предложение описывается двумя натуральными числами: a_i и c_i (1 ≤ a_i ≤ n, 1 ≤ c_i ≤ 10⁶).

Формат выходных данных

В выходной файл необходимо вывести минимальную стоимость покраски забора.

Примеры входных и выходных файлов

Входные данные	Выходные данные
15 2 0+000+++0+0+++0 2 3 3 5	13
1 1 0 1 10	10
1 1 + 1 10	0

Комментарии к примерам

В первом примере надо воспользоваться первым предложением для раскраски первой и последней доски (забор замкнутый, поэтому они идут подряд), и дважды вторым предложением, чтобы раскрасить доски с 3 по 5 и с 9 по 11 (10-я доска уже покрашена, но ее надо покрасить еще раз).