Сувеніри#7715
Ви перебуваєте у відпустці в країні, де в обігу є лише два типи монет: срібні та золоті. Вартість однієї золотої монети в срібних монетах має бути значною, оскільки існують лише ці два типи монет. Хоча це створює певні незручності для торговців, вони не бажають вводити третій тип монет.
Їхня ідея полягає в тому, що вартість срібних монет змінюється так, щоб золота монета коштувала менше срібних монет. Щоб спростити розрахунки, вони об'єднують срібні монети в пакети і дають решту лише золотими та упакованими срібними монетами, але не окремими срібними монетами. Проте вони не змінюють свої ціни, які є кратними вартості срібної упаковки.
Таким чином, торговці повинні округляти решту. Різні продавці використовують різні методи округлення. Чесні торговці округлюють до найближчого значення і в більшу сторону у випадку рівності. Жадібні торговці завжди округлюють вниз. Щедрі торговці завжди округлюють вгору. Продавці також не домовилися про один розмір упаковки, тому всі вони можуть бути різними. Але вони завжди є невід'ємним фактором поточної вартості золотої монети в срібних монетах.
У вас залишилося трохи золотих монет, і ви хочете купити якомога більше сувенірів. Ви вже знаєте різні ціни у всіх торговців на ринку (ціна нижча, ніж коштує одна золота монета), і який торговець є жадібним, щедрим і чесним, а також розміри їх упаковок срібних монет. У вас є час лише один раз пройтися по ринку, тому потрібно відвідати торговців у вказаному порядку. Ви не бажаєте зловживати щедрістю щедрих торговців. Тому якщо ви можете заплатити точну ціну, ви робите це; інакше ви платите рівно однією золотою монетою. Іншим торговцям ви платите або точну ціну, або однією золотою монетою. Ви купуєте не більше одного сувеніра у кожного продавця. Після покупки ви розпаковуєте решту (тобто пакети срібних монет), щоб надалі використовувати монети окремо.
Наприклад, у третьому тесті ви пропускаєте першого продавця і купуєте у другого за золоту монету. Оскільки ви не можете точно заплатити третьому продавцю, то знову використовуєте золоту монету. При обміні двох покупок (шість і вісім срібних монет) ви можете оплатити сувеніри у решти трьох торговців.
Перший рядок містить три цілі числа , і , де позначає вартість однієї золотої монети в срібних монетах, позначає кількість наявних у вас золотих монет і - кількість продавців на ринку (1 < g \le 100, 1 \le c, n \le 100).
Кожен з наступних рядків описує одного продавця. Кожен з цих рядків починається зі слова "greedy", "honest" або "generous", що описує звичку продавця до округлення. За словом слідують два цілі числа p_i і s_i, де p_i позначає розмір упаковки срібних монет, які використовує торговець, а s_i вказує ціну сувеніра у цього торговця в срібних монетах (1 \le p_i \le g, 1 \le s_i < g).
Один рядок, що містить максимальну кількість сувенірів, яке ви можете купити.
Приклад 1
Приклад 2
Приклад 3