Demon's Plan

BackGround

In the Demon's Plan, 108 demons who control the desire are competing in the programming contest day and night. The organizer, Patron, is trying to invite the demons to "Rix-Magna", a place where all the souls gather. Patron wants to send an invitation to a demon who hasn't sent an invitation yet, but he decides to let his familiars do it because the demons are all over the world and it's a hassle to go by himself. Patrons are smart and are trying to allocate which familiars are in charge of which demons so that the familiars work more equally.

Problem

There are N familiars and M demons. The distance between familiar i and devil j is Hi j.

I want each demon to have one familiar. Which familiar will visit which demon will be assigned according to the following conditions.

1. Minimize the maximum difference in the number of demons visited per familiar.
2. Minimize the maximum distance between the visiting demon and the familiar familiar after satisfying 1.

Output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Constraints

• 1 ≤ N ≤ 108
• 1 ≤ M ≤ 108
• 1 ≤ Hi j ≤ 109 (0 ≤ i <N, 0 ≤ j <M) (distance from familiar i to devil j)

Input

The input is given in the following format.

N M H0 0 H0 1… H0 M−1 H1 0 H1 1… H1 M-1 .. .. HN−1 0 HN−1 1… HN−1 M−1

On the first line, the number N of familiars and the number M of demons are given as integers separated by blanks. The distance between the familiar and the devil is given as an integer in the following N lines. Hij represents the distance between familiar i and devil j.

Output

According to the conditions of the problem statement, output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Examples

Input

3 3 1 2 3 2 1 2 3 2 1

Output

0 1

Input

3 5 1 2 3 4 5 5 4 3 2 1 4 3 2 1 5

Output

1 2

inputFormat

outputFormat

Output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Constraints

• 1 ≤ N ≤ 108
• 1 ≤ M ≤ 108
• 1 ≤ Hi j ≤ 109 (0 ≤ i <N, 0 ≤ j <M) (distance from familiar i to devil j)

Input

The input is given in the following format.

N M H0 0 H0 1… H0 M−1 H1 0 H1 1… H1 M-1 .. .. HN−1 0 HN−1 1… HN−1 M−1

On the first line, the number N of familiars and the number M of demons are given as integers separated by blanks. The distance between the familiar and the devil is given as an integer in the following N lines. Hij represents the distance between familiar i and devil j.

Output

According to the conditions of the problem statement, output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Examples

Input

3 3 1 2 3 2 1 2 3 2 1

Output

0 1

Input

3 5 1 2 3 4 5 5 4 3 2 1 4 3 2 1 5

Output

1 2

样例

3 3
1 2 3
2 1 2
3 2 1

0
1

</p>