АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1547. Покраска забора

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

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

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

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

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

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

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

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

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

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

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

Входные данные

Выходные данные

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-я доска уже покрашена, но ее надо покрасить еще раз).

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Школьные олимпиады Вологодской области / Областная олимпиада школьников 2006-2007 /
1546. 1 - Алгоритм Евклида 1547. 1548. 3 - Радио 1549. 4 - Преобразование последовательности 1550. 5 - Скобочки
 
время генерации 0.11 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.