Спорттық бағдарламалау әлемінде әдетте екі форматтағы жарыстарды ажыратады: IOI (International Olympiad in Informatics) және ICPC (International Collegiate Programming Contest). Мысалы, «ЧРК» жарысы ICPC ережелері бойынша өткізіледі.

1. ICPC форматы:

   • Жарысқа бірнеше адамнан тұратын командалар қатысады.

   • Барлық есептер бірдей бағаланады (есеп не шешілген, не шешілмеген).

   • Мақсат — шектеулі уақыт ішінде барынша көп есепті шешу.

   • Шешілген есептердің саны бірдей болған жағдайда, жазасы (айып уақыты) аз команда жоғары орынға ие болады (дұрыс шешім үшін — контест басталған сәттен бастап саналған минуттар саны + әрбір қате жіберу үшін 20 минут айыппұл).

2. IOI форматы:

   • Әрбір қатысушы жеке өнер көрсетеді.

   • Әр есеп 100 баллмен бағаланады, жартылай шешімдер үшін аралық балл алуға болады (мысалы, 30, 70 балл және т.б.).

   • Қатысушының қорытынды нәтижесі — әр есеп бойынша алған ең жоғары (максималды) ұпайлардың жиынтығы (есепте барлық жіберілген шешімдер ішінен тек ең үздік нәтиже ескеріледі).

   • Жалпы ұпайлары тең болған қатысушылар сол орынды бөліседі.

Мысалы, бір оқу-жаттығу IOI-жарысына \(N\) адам қатыссын, олардың нөмірлері \(1\)-ден \(n\)-ге дейін, ал сіздің нөміріңіз — \(1\). Жаттықтырушыңыз сізді бірінші орынға шығарғысы келеді, өйткені ол сізді ерекше жақсы көреді. Осы мақсатқа жету үшін жаттықтырушы қалаған қатысушының (қаласа — сіздің де) белгілі бір есеп бойынша барлық жіберілімдерін «ескермеуге» (толығымен жоюға) болады, сол жіберілімдер ешқашан болмағандай саналады. Бұл әрекет таңдалған қатысушы мен есеп үшін бір батырманы басу арқылы орындалады.

Жойылған шешімдер қайта есептеу кезінде ескерілмейді.

Сіздің қорытынды ұпайыңыз кез келген өзге қатысушының ұпайынан кем болмас үшін, батырманы неше рет ең аз басу керек?

Енгізу

Бірінші жолда \(n\) және \(q\) сандары беріледі (\(2\le n \le 100, 1 \le q \le 1000\)) — қатысушылар саны және жіберілімдер (посылок) саны.

Келесі \(q\) жолдың әрқайсысында \(3\) элемент (токен) бар: \(id\), \(Prob\), \(score\) (\(1\le id \le n\), \(\text{`A'} \le Prob \le \text{`F'}\), \(1 \le score \le 100\)). Бұл «Қатысушы \(id\) \(Prob\) есебі үшін \(score\) ұпай алғанын» білдіреді. Әрбір есеп 'A'-дан 'F'-ке дейінгі бас әріппен белгіленеді.

Шығару

Жалғыз санды шығарыңыз — сіз бірінші орынға шығу үшін ескермеуге (жоюға) қажет ең аз жіберілімдердің (посылок) санын көрсетіңіз.

Мысалдар

Енгізу 1

5 11
1 F 22
1 E 66
2 E 73
2 B 35
2 F 88
3 A 14
3 C 24
3 E 71
3 E 36
5 B 49
4 A 88

Жауап 1

3

Ескертпелер

Егер осылай жоюлардан кейін сізде және қарсыласыңызда тең ұпайлар қалатын болса, екеуіңіз де бірінші орынды бөлісесіздер, және бұл ресми түрде «жеңімпаз» болып саналу үшін жеткілікті.

Бірінші тесттік мысалда: \(1\)-ші қатысушыда — \(88\) ұпай, \(2\)-ші қатысушыда — \(196\) ұпай, \(3\)-ші қатысушыда — \(14 + 24 + 71 = 109\) ұпай, \(4\)-ші қатысушыда — \(88\) ұпай, \(5\)-ші қатысушыда — \(49\) ұпай. \(3\)-ші қатысушының «C» есебін ескермеуге (жоюға), сондай-ақ \(2\)-ші қатысушының «E» және «B» есептерін ескермеуге болады.