Given an MxN matrix with its rows sorted in ascending order and an integer k.

Define a sum S which consists of one element from each row.

Find the kth smallest sum S_k.

Example

Input
[
  [1, 3, 5, 7, 9],
  [2, 4, 6, 8, 10]
]
k = 3

Output
5

Explanation
The third smallest sum is returned from this sequence:
1+2, 1+4, 2+3, 1+6, 2+5, 3+4, and so on