Bạn được cho một mảng hai chiều gồm ~N * M~ số nguyên dương ~a_{i, j} \ (a_{i, j} \leq 10^9)~, với ~1 \leq i \leq N~ và ~1 \leq j \leq M~. Ngoài ra, bạn cũng được cho ~N~ số nguyên dương ~w_i \ (w_i \leq 10^9)~, với ~1 \leq i \leq N~.

Nhiệm vụ của bạn là tìm hai vị trí ~i, j \ (1 \leq i < j \leq N)~, sao cho các số ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}, \ a_{i + 1, 1}, a_{i + 1, 2}, \dots, a_{i + 1, m}, \dots, \ a_{j, 1}, a_{j, 2}, \dots, a_{j, m}~ phân biệt, đồng thời ~w_i + w_j~ là nhỏ nhất, hoặc in ra ~-1~ nếu không tồn tại cặp ~i, j~ thỏa mãn.

Input

• Dòng đầu chứa hai số nguyên dương ~N, M \ (1 \leq N \leq 10^5, \ 1 \leq M \leq 5)~.

• Dòng thứ hai gồm ~N~ số nguyên dươn ~w_1, w_2, ..., w_n~ ~(w_i \leq 10^9)~.

• ~N~ dòng sau, mỗi dòng chứa ~M~ số nguyên dương ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m} \leq 10^9~.

Output

• In ra một số nguyên duy nhất là tổng ~w_i + w_j~ nhỏ nhất, hoặc ~-1~ nếu không tồn tại cặp thỏa mãn.

Scoring

Sample Input 1

4 4
2 7 6 1
10 7 11 5
19 9 8 7
15 18 16 1
7 15 20 9

Sample Output 1

13