ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Internal Contest March'2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. In the Army Now

Time limit: 0.5 second
Memory limit: 64 MB
The sergeant ordered that all the recruits stand in rows. The recruits have formed K rows with N people in each, but failed to stand according to their height. The right way to stand in a row is as following: the first soldier must be the highest, the second must be the second highest and so on; the last soldier in a row must be the shortest. In order to teach the young people how to form rows, the sergeant ordered that each of the recruits jump as many times as there are recruits before him in his row who are shorter than he. Note that there are no two recruits of the same height.
The sergeant wants to find which of the rows will jump the greatest total number of times in order to send this row to work in the kitchen. Help the sergeant to find this row.


The first line contains integers N and K (2 ≤ N ≤ 10000; 1 ≤ K ≤ 20). Each of the following K lines contains N different integers from 1 to N. The recruits in each row are numbered according to their height (1 — the highest, N — the shortest). Each line shows the order in which the recruits stand in the corresponding row. The first integer in a line is the number of the first recruit in a row and so on. Therefore a recruit jumps as many times as there are numbers which are greater than his number in the line before this number.


You should output the number of the row in which the total amount of jumps is the greatest. If there are several rows with the maximal total amount of jumps you should output the minimal of their numbers.


3 3
1 2 3
2 1 3
3 2 1
Problem Author: Nikita Shamgunov
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session
To submit the solution for this problem go to the Problem set: 1090. In the Army Now