593. Find the Kth Smallest Sum of a Matrix With Sorted Rows

0

Hard

Given a matrix mat with m rows and n columns, where the rows are sorted in non-decreasing order, and an integer k, you need to choose one element from each row to form an array. Find and print the kth smallest sum among all possible arrays.

Input Format

The input consists of the following lines: - The first line contains the number of rows in the matrix (m). - The second line contains the number of columns in the matrix (n). - The third line contains the elements of the matrix, separated by spaces. - The fourth line contains the value of k.

Output Format

Print the kth smallest sum among all possible arrays as an integer.

Example

Input

2 3 1 3 11 2 4 6 5

Output

7

Constraints

The matrix has m rows and n columns, where m is equal to the length of the matrix and n is equal to the length of each row. The values of m and n are between 1 and 40, inclusive. The elements in the matrix range from 1 to 5000. The value of k is between 1 and the minimum of 200 and n raised to the power of m, inclusive. Each row of the matrix is sorted in non-decreasing order.