Отправлено: 22.04.12 14:01. Заголовок: [C4] Задача про плотника Ивана

Недавно эту задачу опубликовали вконтакте. Говорят, кто её сможет решить, тот готов к егэ =). Это какая тема проверяется? Как решать такую
задачу:

Плотник Иван получил N заказов. Просматривая заказы он заметил, что для их выполнения нехватает M станков. Однако есть заказы, не требующие всех станков для выполнения, но каждый заказ требует хотя бы один из них. Иван может либо заказать, либо купить станок для выполнения заказа. Т.к. на каждый заказ требует разный объем работ, значит и разное время работы на станке, так что стоимость аренды может зависеть от работы, выполняемой на станке. Стоимость покупки никак не зависит от выполняемых на этом станке работ. Купленный станок может быть использован для любого количества работ бесплатно. Если Ивану стоимость выполнения заказа кажется слишком высокой, то он
может отказаться от него. Напишите программу, которая поможет Ивану понять от какого заказа отказаться и какие станки купить, что бы максимизировать свой доход.

Пример:
N=2 M=3
Заказы:
Доход от O1 100
Доход от O2 100
Станки (стоимость покупки):
M1 50
M2 80
M3 110
Для заказа O1 требуются станки M1 и M2 с ценами за аренду в 30 и 20
соотв.
Для заказа O2 требуются станки M1 и M3 с ценами за аренду 40 и 80
соответственно.
Здесь два решения, ведущие к максимальному доходу в 50:
Отказаться от O2, завершить O1. Арендовать M1, M2.
Завершить оба O1 и O2. Купить M1, арендовать M2 и M3.

На вход программе подается 2 числа N (1<=N<=1200) и M (1<=M<=1200).
Следующие N блоков строк описывают заказы. Блоки состоят из:
Первая строка блока i содержит 2 числа доход от завершения Vi
(1<=Vi<=5000) заказа Oi и количество станков mi (1<=mi<=M) необходимых
для выполнения заказа Oi. Следующие mi строк описывают станки. Строки
состоят из: номера станка j (1<=j<=M) необходимого для завершения заказа
и стоимости аренды Rij (1<=Rij<=20000) станка j для выполнения заказа i.
Следующие M строк содержат по одному числу - стоимости покупки i-го
станка Si (1<=Si<=20000).

Вывести нужно всего одно число - максимальных доход.

Пример:
Входной файл:
2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
Выходной файл:
50

 Отправлено: 22.04.12 18:45. Заголовок: Это олимпиадная зада..

Это олимпиадная задача на оптимизацию, на ЕГЭ таких не будет.