Вимірювання молока (Срібло)#10513

Вимірювання молока (Срібло)

1 секунда

128 мегабайтів

Складна

Спочатку кожна корова фермера Джона виробляє $g$ галонів молока на день. Оскільки надій корови може з часом змінюватися, фермер Джон вирішує періодично вимірювати кількість виробленого молока і записувати результати в журнал. Записи в його журналі виглядають так:

35 1234 -2
14 2345 +3

Перший запис означає, що в день $35$ надій корови $1234$ був на $2$ галони меншим, ніж під час попереднього вимірювання. Наступний запис означає, що в день $14$ надій корови $2345$ збільшився на $3$ галони порівняно з попереднім вимірюванням. Фермер Джон встигає проводити не більше одного вимірювання в будь-який день. На жаль, він трохи неорганізований і записує результати вимірювань не обов'язково в хронологічному порядку.

Щоб підтримувати мотивацію своїх корів, фермер Джон з гордістю розміщує на стіні свого корівника фотографії всіх корів, які на даний момент мають найбільший надій. Якщо кілька корів мають однаковий максимальний надій, він розміщує фотографії всіх цих корів. Визначте кількість днів, у які фермеру Джону довелося б змінити цю експозицію.

Зауважте, що у фермера Джона дуже велике стадо корів. Тому, хоча в його журналі можуть бути відмічені корови, які змінили свій надій, завжди існує достатньо багато інших корів, чий надій залишається рівним $g$ галонам.

Вхідні дані

Перший рядок містить кількість вимірювань $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), які проводить фермер Джон, а також число $g (1 \leq g \leq 1 0^{9})$ g~(1 \le g \le 10^9). Кожен із наступних $n$ рядків містить одне вимірювання у описаному вище форматі: день (ціле число в діапазоні $1 \dots 1 0^{6}$ 1 \ldots 10^6), цілочисельний ID корови (в діапазоні $1 \dots 1 0^{9}$ 1 \ldots 10^9) і зміну її надою порівняно з попереднім вимірюванням (ненульове ціле число). Надій кожної корови завжди залишатиметься в діапазоні $0 \dots 1 0^{9}$ 0 \ldots 10^9.

Вихідні дані

Виведіть кількість днів, у які фермеру Джону необхідно було змінити свою мотиваційну експозицію.

Приклади

Приклад 1