Задача E. Осенний лист ≡

Условие

Тимофей очень хочет победить на региональном этапе Всероссийской олимпиады школьников по экологии. На этом этапе предусмотрен тур защиты проектов, поэтому в рамках своего исследования мальчик каждый день наблюдает за берёзой, растущей напротив окна его квартиры. За лето на ней распустилось ровно n зелёных листочков. В течение осени зеленый лист сначала становился желтым, а потом опадал. Тимофею было интересно, сколько листьев останется на берёзе через k дней.

К сожалению, юный эколог выбрал не самый удачный способ подсчета листьев. В каждый из k дней он выбирал какой-нибудь из двух цветов (зеленый или желтый), подсчитывал, какая часть оставшихся на берёзе листьев имеет такой цвет, и записывал эту дробь на бумажку. Наступила зима, и Тимофей не может вспомнить точное количество оставшихся листьев на берёзе. Помогите ему!

Для определенности считайте, что каждый день с берёзы опадало наименьшее возможное количество листьев.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и k. В следующих k строках через пробел расположены символ g или y, обозначающий цвет листьев подсчитанной части — зелёный или желтый соответственно, а также два целых числа a_i, b_i — числитель и знаменатель несократимой дроби, выражающей эту часть. Гарантируется непротиворечивость входных данных.

Формат выходных данных

Выведите одно неотрицательное целое число — максимально возможное количество оставшихся на берёзе листьев после k дней.

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ k ≤ 50

0 ≤ a_i < b ≤ 1000

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при k = 1, получат не менее 20 баллов.

Пояснение к примеру

В примере дана берёза, на которой летом было 100 листьев и 5 дней наблюдения. В первый день на берёзе было 34 зеленых листьев. Тогда всего получается 75 зеленых и 25 желтых листьев.

Во второй день на берёзе было 12 желтых листьев. Ни одного листочка не опало, а 25 зелёных листочков пожелтело и тогда на дереве 50 зелёных и 50 желтых листьев.

В третий день на берёзе было 57 зеленых листьев. Без 30 опавших жёлтых листочков не обойтись. На дереве 50 зелёных и 20 желтых листьев.

В четвертый день на берёзе было 45 желтых листьев. 36 зелёных листьев пожелтели. На дереве 14 зелёных и 56 желтых листьев.

В последний пятый день на берёзе было 16 зелёных листьев. Три зелёных листочка пожелтели и опали. Один желтый листочек тоже опал. На дереве 11 зелёных и 55 желтых листьев. Всего на берёзе осталось 66 листов.

Примеры тестов

100 5
g 3 4
y 1 2
g 5 7
y 4 5
g 1 6

66