Задача B. Неразменная монета – II
Задачу добавил: alef
Успешно сдано решений: 27
Лейтенант Сергиенко, прервавший эксперименты Саши Привалова с неразменной монетой, уверял, что были случаи, когда таким образом накапливали на «Запорожец». Может, конечно, это и было преувеличением… Ваша задача – посчитать, какую сумму мог «заработать» обладатель неразменной монеты, используя ее при оплате товаров в течение дня при следующих условиях. Соловец – город маленький, и в нем отыщется не более R точек (магазинов, закусочных, киосков и т.п.), где можно что-то приобрести или за что-то заплатить. Ни в одной из этих точек не следует появляться более двух раз в течение дня – это может вызвать подозрение. В каждой из этих точек, к тому же, ассортимент и количество товаров ограничены. Наконец, кроме неразменной монеты, у ее обладателя в начале имеется некоторая (тоже ограниченная) сумма, поэтому он не может приобрести любой товар.
Примечание
«Заработком» считаются только деньги, приобретенный товар является неликвидным активом.
Формат входного файла input.txt
Первая строка содержит три целых числа – N, S и R, где N – номинал неразменной монеты, выраженный в копейках (1<=N<=1000), S (0<=S<=10000) – сумма (в копейках), имеющаяся вначале у обладателя неразменной монеты (неразменная монета в эту сумму не включается), R – количество точек, где можно использовать монету. В каждой из следующих R строк содержится информация о товарах (услугах и пр.) в описанном ниже формате. В начале каждой строки записано целое число M (0<=M<=10) – количество различных товаров (услуг и пр.), предоставляемых данной точкой. За ним через пробел следует M пар целых чисел Cj, Kj, первое из которых представляет собой цену товара, второе – количество этого товара, имеющееся в наличии.
Формат выходного файла output.txt
Первая строка – целое число A – выраженная в копейках максимально возможная сумма, которую может «заработать» в течение дня обладатель неразменной монеты.
Пример входного файла
4 100 2
1 2 2
1 3 3
Пример выходного файла
6