Експерименти


с. 1

Експерименти

Младият програмист Пиер много обича нестандартното. Затова избра да продължи професионалната си кариера в новаторската фирма “Експерименти за дома”, където участва в не един интересен проект. Например: “Охлаждане на компютър с пералня”, “Разпознаване на USB леген със солена вода”, “Електронно управление на производството на кисело зеле”, “Домашна дискотека с микровълнова печка” и още много други.

След приключване на отминалата успешна година, в “Експерименти за дома” започнаха да планират работата за настоящата. Много чуждестранни производители им предлагат да извършат експерименти с техни продукти, обещавайки солидно заплащане. За извършването на всеки експеримент, обаче, ще са нужни куп уреди и приспособления, включително и доста скъпи, които ще трябва да бъдат закупени от фирмата на Пиер. За щастие повечето уреди и приспособления могат да бъдат използвани в няколко експеримента и така, при добро планиране, фирмата може да увеличи печалбата си.

По традиция ръководството възложи на най-младия във фирмата да реши тази нелека задача. И сега Пиер се чуди какво да направи, за да донесе на фирмата си колкото може по-голяма печалба.

Пиер може да избира измежду N (1 ≤ N ≤ 3000) експеримента. Всеки експеримент може да бъде изпълнен не повече от един път, като за изпълнението фирмата ще получи определено възнаграждение. За да бъде осъществен един експеримент е необходимо да бъдат закупени един или повече измежду M зададени уреди (1 ≤ M ≤ 3000). За всеки уред се знае цената му. Веднъж закупен, един уред може да се използва във всеки експеримент, за който е необходим. Печалбата на фирмата се определя от разликата между получената за извършените експерименти сума и сумата, изразходвана за закупуване на необходимите уреди. Вашата задача е да напишете програма, която да определи кои уреди да бъдат закупени, така че изпълнявайки всички възможни експерименти с тези уреди, да се постигне колкото може по-голяма печалба.

Първият ред на входния текстов файл EXP.INP съдържа двете цели числа N и М, разделени с един интервал. Всеки от следващите N реда описва по един експеримент. Редът започва с две цели числа Ci (1 ≤ Ci ≤ 1000000) и Ui (1 ≤ Ui ≤ M), задаващи съответно цената на експеримента и броя на необходимите за него уреди. На същия ред следват Ui различни числа в интервала от 1 до M, разделени с по един интервал, които задават номерата на необходимите за експеримента уреди. След описанието на експериментите следват M реда, всеки един от които съдържа по едно естествено число Pj - цената на поредния уред (1 ≤ Pj ≤ 1000000). Уредите са номерирани с числата от 1 до М в реда, по който са зададени цените им във входния файл.

Първият ред на изходния текстов файл EXP.OUT съдържа едно число P в интервала от 1 до M – броя на закупените уреди. На втория ред трябва да има P различни числа в интервала от 1 до M, разделени с по един интервал – номерата на уредите, които фирмата трябва да закупи.

Оценяването става по следния начин. Определят се всички експерименти, които могат да бъдат изпълнени с определените от програмата уреди и се пресмята печалбата на фирмата. Ако печалбата е отрицателна, тя ще бъде приета за 0. За всеки тест максимален брой точки ще получи състезателят, чиято програма е постигнала най-голяма печалба. Всички останали решения ще получат точки пропорционално на постигнатата печалба, като за печалба 0 ще бъдат получени 0 точки.


ПРИМЕР
Вход – EXP.INP

3 4


20 2 1 2

10 2 2 3


15 2 2 4

5

10



10

5
Възможен изход – EXP.OUT



3

1 2 4
с. 1

скачать файл