Кто на табло?

На школьном турнире несколько классов набирают очки. После каждого события (кому-то добавили очки) табло подсвечивает лидера — класс с наибольшей суммой очков. Если лидеров несколько (ничья по максимуму), табло подсвечивает класс с меньшим номером.

Тебе дали запись всех событий. Посчитай, сколько раз менялся подсвеченный лидер, если сравнивать табло после соседних событий: между 1-м и 2-м, между 2-м и 3-м, ..., между (n−1)-м и n-м.

Формат ввода

В первой строке два целых числа k и n — число классов и число событий. Далее идут n строк, в каждой: c и p — номер класса, которому добавили очки, и сколько очков добавили.

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

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

Ограничения

• 1 ≤ k ≤ 2000
• 1 ≤ n ≤ 2000
• 1 ≤ c ≤ k
• 0 ≤ p ≤ 1000000

Пример

Ввод:

3 5
2 2
3 2
2 1
1 5
3 10

Вывод:

2

Ключевое наблюдение: табло после каждого события зависит только от текущих сумм очков классов. Значит, можно честно «проиграть» все события по порядку.

Приём: симуляция (пошаговое обновление состояния) + поиск максимума. Ограничения маленькие (k, n ≤ 2000), поэтому пересчитывать лидера полным просмотром всех классов после каждого события успевает.

План:

• Заведи массив scores[1..k], сначала все нули.
• Держи prev_leader — кто был подсвечен после предыдущего события.
• Для каждого события (c, p):
• сделай scores[c] += p.
• найди текущего лидера: класс с максимальным scores[i], а при равенстве — с меньшим номером.
• удобно обновлять так: if s > best or (s == best and i < best_id): ...
• если это не первое событие и лидер изменился (best_id != prev_leader), увеличь счётчик смен.
• присвой prev_leader = best_id.
• Выведи счётчик.

Сложность: O(n * k) по времени (до 4 млн сравнений) и O(k) по памяти.

Частая ошибка: засчитать «первого лидера» как смену. Смены считаются только между соседними событиями, поэтому сравнение начинается со 2-го события.