Nth Largest Number

Time limit1sMemory limit12 MB

Summary
Given an N x N matrix where each column is sorted top to bottom, find the Nth largest value among all N^2 entries efficiently.
Level

Medium6 of 10

Topics
Binary search, Matrix, Heap
Solved
No attempts yet

Problem

An N × N table is filled with N^2 distinct integers. Each number is greater than the number directly above it, so every column increases from top to bottom.

The following table shows one possible table when N = 5.

1279155
13811196
2110263116
4814283525
5220324149

Given such a table, find the Nth largest number among all N^2 numbers.

Input

The first line contains N (1 ≤ N ≤ 1,500). Each of the next N lines contains N integers. Every number written in the table is an integer between -10^9 and 10^9, inclusive.

Output

Print the Nth largest number on the first line.

Examples1

  1. Example 1

    Input
    5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49
    Expected output
    35