Servers

The Greek Universities and Technological Educational Institutes Network http://www.gunet.gr has developed a cluster of ~N~ web servers. Each server:

• manages the same ~M~ pages,
• maintains a counter for each page, which increments by ~1~ when that page is requested from the server, and
• keeps the values of these counters sorted in descending order.

Problem:

Develop a program in one of the IOI languages that, given the number of requests for each page, for each server and sorted, finds the pages with the ~K~ most requests across all servers.

Example:

For ~N = 5~ servers and ~M = 5~ pages:

$$\displaystyle \begin{array}{|c|c|c|c|c|} \hline S1 & S2 & S3 & S4 & S5 \\ \hline 3 \mapsto 99 & 1 \mapsto 91 & 1 \mapsto 92 & 3 \mapsto 74 & 3 \mapsto 67 \\ \hline 1 \mapsto 66 & 3 \mapsto 90 & 3 \mapsto 75 & 1 \mapsto 56 & 4 \mapsto 67 \\ \hline 0 \mapsto 63 & 0 \mapsto 61 & 4 \mapsto 70 & 2 \mapsto 56 & 1 \mapsto 58\\ \hline 2 \mapsto 48 & 4 \mapsto 07 & 2 \mapsto 16 & 0 \mapsto 28 & 2 \mapsto 54 \\ \hline 4 \mapsto 44 & 2 \mapsto 01 & 0 \mapsto 01 & 4 \mapsto 19 & 0 \mapsto 35 \\ \hline \end{array}$$

Explanation: The pages are numbered from ~0~ to ~M - 1~. On server ~S1~, page ~3~ has been requested ~99~ times, page ~1~ ~66~ times, page ~0~ ~63~ times, and so on. The total requests submitted for the ~5~ pages were:

$$\displaystyle \begin{array}{|c|} \hline Top \;\; 5 \\ \hline 3 \mapsto 405 \\ \hline 1 \mapsto 363 \\ \hline 4 \mapsto 207 \\ \hline 0 \mapsto 188 \\ \hline 2 \mapsto 175 \\ \hline \end{array}$$

For ~K = 2~, the two most popular pages are ~3~ and ~1~.

Input Files:

The input files named servers.in are text files with the following structure: The first line contains three integers ~M~, ~N~, and ~K~. The number ~M~ of hosted pages ~(5 \le M \le 10.000)~.
Note that the first page is numbered 0. The number ~N~ of servers ~(5 \le N \le 1.000)~. The number ~K~ of the most popular pages requested ~(2 \le K \le M)~. The numbers are separated in pairs by a single space. The next ~M~ lines contain ~N~ pairs of integers. The first line has for each server the page most requested, the second the next most requested, and so on. In each pair, the first integer is the page number and the second is how many times it was requested. All numbers are separated by a single space. No page will be requested by any server more than ~500.000~ times.

Output Files:

The output files named servers.out are text files with the following structure. They have exactly ~K~ lines. Each line contains two integers: the page number and the total number of times it was requested. The pages are sorted in descending order of total requests (most popular first). Pages with the same total number of requests can appear in any order. Also, if the ~(K+1)~-th most popular page has the same total number of requests as the ~K~-th, it does not matter which of the two will be displayed in the output file, and which one will not be displayed at all.

Example of Input - Output Files:

STDIN (servers.in)

5 5 2
3 99 1 91 1 92 3 74 3 67
1 66 3 90 3 75 1 56 4 67
0 63 0 61 4 70 2 56 1 58
2 48 4 07 2 16 0 28 2 51
4 44 2 01 0 01 4 19 0 35

STDOUT (servers.out)

3 405
1 363

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.