Indian National Olympiad in Informatics

Related:

Online Programming Contest, 10-11 June 2006

IARCS home > OLYMPIAD

Advanced Division

Problem 1: Red Card, (K Narayan Kumar, CMI)

The government of Siruseri issues a red coloured identity card to its Permanent Residents. A Permanent Resident of Siruseri is for all practical purposes a citizen of Siruseri. This has encouraged a large number of alien workers to apply for this status symbol.

The process of obtaining a red card is rather complicated and involves N stages. At each stage, an officer of the Siruseri government will examine the papers submitted by the applicant and verify that it meets some specific requirements. In order to speed up the process, the government has appointed M officials to handle the papers at each stage. Unfortunately, not all these officials are equally efficient. However, as part of the "Open Government" policy, the Siruseri government has released data on how long each official takes to process an application (in number of days).

In order to prevent the efficient officials from being swamped, the M×N officials have been grouped into M channels. A channel contains one official for each stage. An applicant may choose any channel and may also switch channels as he clears the N stages. However, these changes are restricted. A channel change is permitted only in between stages and not in the middle of a stage. Moreover, an applicant in channel i can only change to channel i+1. However, an application is also allowed to shift from channel M to channel 1. There is no limit on the number of channel changes.

For example, here is a description of the efficiency of the officials with 3 channels and 4 stages:

Channel 1     2 6 1 8 
Channel 2     3 6 2 6 
Channel 3     4 2 3 6

In this example, one option would be to simply stick to channel 1, which would take 17 days. However, an applicant could start with Channel 2, shift to Channel 3 for stage 2, then shift to Channel 1 for stage 3 and finally shift to Channel 2 for stage 4. This would take 12 days. You can check that an applicant cannot do better than this.

Your task is to determine the minimum number of days in which an applicant can complete all the stages.

Input format

The first line contains two integers N and M, indicating the number of stages and the number of channels, respectively. This is followed by M lines containing N integers each. The j^th integer on line i+1 (1 ≤ i ≤ M) is the time taken by the j^th stage official on channel i.

Output format

A single integer indicating the minimum number of days required to complete all the stages.

Test Data:

You may assume 1 ≤ N ≤ 2000 and 1 ≤ M ≤ 1000.

Example:

Here is the sample input and output corresponding to the example above.

Sample Input

Sample Output