Фермер Питер огородил свое новое пастбище отличным забором, состоящим из n досок. Забор имеет форму замкнутой ломаной. К сожалению, некоторые из этих досок покрашены в белый цвет, а некоторые — нет. Разумеется, фермер хочет, чтобы его пастбище было огорожено красивым забором, поэтому он решил покрасить весь забор в белый цвет. 
Для покраски фермеру порекомендовали нанять компанию «В&М», расположенную в соседнем поселке. Он обратился в эту компанию, и ему предложили сделать заказ на покраску участков забора. Каждый заказ должен быть сформирован из множества предложений компании. Каждое предложение характеризуется количеством окрашиваемых досок ai и стоимостью соответствующей работы ci, и заключается в том, что за сумму ci рублей сотрудники компании покрасят любые ai идущих подряд досок в белый цвет.
В процессе выполнения заказа разрешается доску красить в белый цвет сколько угодно раз, при этом уже окрашенные доски заново красить не требуется (хотя разрешается), а еще не окрашенные доски надо обязательно покрасить.
Требуется написать программу, с помощью которой можно определить, какую минимальную сумму фермер Питер заплатит компании «В&М» за то, что весь его забор будет выкрашен в белый цвет.

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

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



Примеры входных и выходных файлов
fence.in                                                            fence.out
15 2
0+000+++0+0+++0                                                   13
2 3
3 5    

чет я не понял как это число получилось?

Я сам  не понял как это так...

DeadLine, чесн слово , я не умею писать код при этом не поняв что он должен делать 

DeadLine, а ты уверен, что абсолютно правильно привёл условие? 
Это перевод? Если да, то кто переводил? 
Можешь привести оригинал? (Лучше отсканированный вариант.)

Если я всё правильно понял то оно получилось так:

Первый заказ:
   цена 5
   было  0+000+++0+0+++0
   стало 0+++++++0+0+++0
Второй заказ:
   цена 5
   было  0+++++++0+0+++0
   стало 0+++++++++++++0
Третий заказ:
   цена 3
   было  0+++++++++++++0
   стало +++++++++++++++ (не забываем - забор замкнутый)

Итого: 13.

Это сообщение отредактировал(а) Strannik - 4.2.2007, 18:03

Strannik, точняк! 

Какие мы, млин, с Romikgy невнимательные. 

А уж то, что автор не смог объяснить, булыжник большущий ему в полисад. 

Вообще-то я честно не понял задачу.И как решать ее я непредставляю.А это оригинал условий ибо она была на русском

не понял этого решения 

Сначала красим три доски который непокрашеные рядом, платим 5. Потом красим три доски где две непокрашеные через покрашенную, её прийдется по второму разу красить, платим снова 5. И наконец красим нач. и кон. доску забора(они ведь рядом, забор замкнут), платим 3. 

Что конкретно непонятно?

Как это 

связано с этим

?

Это


 является решением для этого случая. (Это- пример, покзывающий формат входных данных).

Если автору топика подходит ответ, вопросов нет 
но я не могу понять откуда взлось



из

этих чисел?

Вообще я хотел увидеть реализацию на одном из языков приведенных в названии

Romikgy, то что я привёл не есть решение задачи, это есть разбор и анализ примера входных данных. А решения я собственно ещё не придумал...