Сувениры
Вы находитесь в отпуске в стране, где используются только два типа монет: серебряные и золотые. Относительная стоимость одной золотой монеты по сравнению с количеством серебряных монет должна быть большой, потому что существуют только эти два типа монет. Хотя это довольно неудобно для торговцев, они не хотят иметь дело с третьим типом монет.
Их идея заключается в том, что стоимость серебряных монет изменяется таким образом, что золотая монета стоит меньше серебряных монет. Чтобы заявить о себе, они связывают серебряные монеты в пакеты и дают сдачу только золотыми и упакованными серебряными монетами, но не отдельными серебряными монетами. Однако они не меняют свои цены, кратные стоимости серебряной упаковки.
Таким образом, торговцы должны округлить сдачу. Разные продавцы используют разные методы округления. Честные торговцы округляют до ближайшего значения и в большую сторону в случае равенства. Жадные торговцы всегда округляют вниз. Щедрые торговцы всегда округляют вверх. Продавцы также не договаривались об одном размере упаковки, поэтому все они могут быть разными. Но они всегда являются неотъемлемым фактором текущей стоимости золотой монеты в серебряных монетах.
У Вас осталось немного золотых монет, и Вы хотите купить как можно больше сувениров. Вы уже знаете разные цены у всех торговцев на рынке (цена ниже, чем стоит одна золотая монета) и какой торговец является жадным, щедрым и честным, а также размеры их упаковок серебряных монет. У Вас есть время только один раз пройтись по рынку, поэтому нужно посетить торговцев в указанном порядке. Кроме того, Вы не хотите использовать щедрых торговцев. Таким образом, если Вы можете заплатить точную цену, то сделаете это; в противном случае заплатите ровно одной золотой монетой. Вы платите другим торговцам либо точную цену, либо одну золотую монету. Вы покупаете не более одного сувенира у каждого продавца. Затем Вы распаковываете сдачу, то есть пакеты с серебряными монетами, так что Вы можете использовать монеты отдельно.
Например, в третьем тесте Вы пропускаете первого продавца и покупаете у второго за золотую монету. Поскольку Ввы не можете точно заплатить третьему продавцу, то снова используете золотую монету. При обмене двух покупок (шесть и восемь серебряных монет) Вы можете оплатить сувениры у оставшихся трех торговцев.
Входные данные
Первая строка содержит три целых числа g, c и n, где g обозначает стоимость одной золотой монеты в серебряных монетах, c обозначает количество имеющихся у вас золотых монет и n - количество продавцов на рынке (1 < g ≤ 100, 1 ≤ c, n ≤ 100).
Каждая из следующих n строк описывает одного продавца. Каждая из этих строк начинается со строки “greedy”, “honest” или “generous”, описывающей привычку продавца к округлению. За строкой следуют два целых числа p[i] и s[i], где p[i] обозначает размер упаковки серебряных монет, которые использует торговец, а s[i] указывает цену сувенира у этого торговца в серебряных монетах (1 ≤ p[i] ≤ g, 1 ≤ s[i] < g).
Выходные данные
Одна строка, содержащая максимальное количество сувениров, которое Вы можете купить.