Сувеніри
Ви перебуваєте у відпустці в країні, де в обігу є лише два типи монет: срібні та золоті. Вартість однієї золотої монети в срібних монетах має бути значною, оскільки існують лише ці два типи монет. Хоча це створює певні незручності для торговців, вони не бажають вводити третій тип монет.
Їхня ідея полягає в тому, що вартість срібних монет змінюється так, щоб золота монета коштувала менше срібних монет. Щоб спростити розрахунки, вони об'єднують срібні монети в пакети і дають решту лише золотими та упакованими срібними монетами, але не окремими срібними монетами. Проте вони не змінюють свої ціни, які є кратними вартості срібної упаковки.
Таким чином, торговці повинні округляти решту. Різні продавці використовують різні методи округлення. Чесні торговці округлюють до найближчого значення і в більшу сторону у випадку рівності. Жадібні торговці завжди округлюють вниз. Щедрі торговці завжди округлюють вгору. Продавці також не домовилися про один розмір упаковки, тому всі вони можуть бути різними. Але вони завжди є невід'ємним фактором поточної вартості золотої монети в срібних монетах.
У вас залишилося трохи золотих монет, і ви хочете купити якомога більше сувенірів. Ви вже знаєте різні ціни у всіх торговців на ринку (ціна нижча, ніж коштує одна золота монета) і який торговець є жадібним, щедрим і чесним, а також розміри їх упаковок срібних монет. У вас є час лише один раз пройтися по ринку, тому потрібно відвідати торговців у вказаному порядку. Крім того, ви не хочете використовувати щедрих торговців. Таким чином, якщо ви можете заплатити точну ціну, то зробите це; в іншому випадку заплатите рівно однією золотою монетою. Ви платите іншим торговцям або точну ціну, або одну золоту монету. Ви купуєте не більше одного сувеніра у кожного продавця. Потім ви розпаковуєте решту, тобто пакети зі срібними монетами, так що ви можете використовувати монети окремо.
Наприклад, у третьому тесті ви пропускаєте першого продавця і купуєте у другого за золоту монету. Оскільки ви не можете точно заплатити третьому продавцю, то знову використовуєте золоту монету. При обміні двох покупок (шість і вісім срібних монет) ви можете оплатити сувеніри у решти трьох торговців.
Вхідні дані
Перший рядок містить три цілі числа 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).
Вихідні дані
Один рядок, що містить максимальну кількість сувенірів, яке ви можете купити.