Milk Measurement#10513
Each of Farmer John's cows initially produces gallons of milk per day. Since a cow's milk production may change over time, Farmer John decides to take periodic measurements and record them in a log book. Entries in his log look like this:
35 1234 -2
14 2345 +3 The first entry indicates that on day , cow 's milk production was gallons lower than when it was last measured. The next entry indicates that on day , cow 's milk production increased by gallons compared to its previous measurement. Farmer John has enough time to make at most one measurement on any given day. Unfortunately, he is a bit disorganized and does not necessarily record his measurements in chronological order.
To keep his cows motivated, Farmer John proudly displays on the wall of his barn pictures of all cows that currently have the highest milk production. If several cows are tied for the highest milk production, he displays all of their pictures. Determine the number of days on which Farmer John would have needed to change this display.
Note that Farmer John has a very large herd of cows. Thus, although some cows are recorded in his log book as changing their milk production, there are always plenty of other cows whose milk production remains at gallons.
The first line contains the number of measurements n~(1 \le n \le 10^5) that Farmer John makes, followed by g~(1 \le g \le 10^9). Each of the next lines contains one measurement in the format described above, specifying a day (an integer in the range 1 \ldots 10^6), the integer ID of a cow (in the range 1 \ldots 10^9), and the change in her milk production since it was last measured (a nonzero integer). Each cow's milk production will always remain in the range 0 \ldots 10^9.
Print the number of days on which Farmer John needs to adjust his motivational display.
Example 1