Santa Claus, Snow Maiden and sweets
Problem
Father Frost and the Snow Maiden come to children's matinees with a bag of sweets. Santa Claus divides the sweets equally among all the children present (there are never more than 100 children at a matinee), and gives the remaining sweets to the Snow Maiden. The Snow Maiden each time writes down the number of sweets received in a notebook. If the sweets are divided among all the children without a trace, the Snow Maiden receives nothing and does not write anything down. When the matinees were over, Santa Claus became interested in what number the Snow Maiden wrote down most often.
Father Frost and Snow Maiden – magicians, so the number of N matinees they have attended can be very large.
Write a program that will solve this problem. Before the text of the program, briefly describe the algorithm for solving the problem, indicate the programming language used and its version. It is desirable that the program be efficient both in terms of running time and in terms of memory used.
A program will be considered memory efficient if the memory used does not depend on the size of the input data (that is, the number of matinees). A program will be considered time efficient if the increase in the size of the input data N by t times (t – any number) does not increase its running time more than t times.
Input
The first line contains a single positive integer – number of matinees N. Each of the following N lines contains two integers: D – the number of children who came to the next matinee; K – the number of sweets in Santa Claus's bag on this matinee.
The following relationships are guaranteed: \(1 <= N <= 10000\), \(1 <= D <= 100\) (for each D), \(D <= K < = 1000\) (for each pair D, K)
Output
The program should output a single number – the one that the Snow Maiden wrote down most often. If several numbers were written equally often, you need to print the larger of them. If the Snow Maiden has never recorded anything, print zero.
Examples
| # |
Input |
Output |
| 1 |
7
10 58
15 315
20408
100 1000
32 63
32 63
11 121
|
31 |