Trên bàn cờ kích thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm giao ở hàng \(i\) (\(1 \le i \le n\)), cột \(j\) (\(1 \le j \le n\)) được gọi là ô \((i,j)\), ô này có trọng số là \(w_{ij}\). Cần đặt đúng \(k\) quân hậu lên bàn cờ để không có hai quận hậu nào chiếu nhau. Nhắc lại, hai quân hậu chiếu nhau nếu chúng được đặt trên cùng hàng hoặc cùng cột hoặc trên cùng đường chéo.

Yêu cầu: Gọi \(s\) là tổng trọng số các ô có quân hậu đặt, tìm cách đặt để \(s\) là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên \(n,k\) (\(k \le n \le 8\)).
• Dòng thứ \(i\) (\(1 \le i \le n\)) trong \(n\) dòng sau, mỗi dòng chứa \(n\) số nguyên không âm mô tả trọng số của bảng (các số không vượt quá \(10^6\)).

Output

• Một dòng chứa một số là tổng \(s\) lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(k \le 3\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 2
1 0 2
0 0 2
0 2 0

4

Với dãy số nguyên dương \(A = (a_1,a_2,...,a_n)\) và số nguyên dương \(k\), tạo dãy \(A^k\) gồm \(m = n \times k\) phần tử bằng cách ghép liên tiếp \(k\) lần dãy \(A\), cụ thể \(A^k = (a_1,a_2,...,a_n,...,a_1,a_2,...,a_n)\). Một đoạn \(d\) phần tử liên tiếp trên dãy \(A^k\) bắt đầu từ phần tử thứ \(i\) (\(1 \le i \le m-d+1\)) gồm các phần tử \(i,i+1,...,(i+d-1)\) được gọi là đoạn đẹp nếu điều kiện sau thỏa mãn:

\(2 \times min(a_i,a_{i+1},...,a_{i+d-1}) > \frac{a_i + a_{i+1} + ... + a_{i+d-1}}{d}\)

Yêu cầu: Cho \(A = (a_1,a_2,...,a_n)\) và hai số nguyên dương \(k,d\), hãy đếm chỉ số \(i\) (\(1 \le i \le m-d+1\)) mà đoạn gồm \(d\) phần tử liên tiếp bắt đầu từ phần tử \(i\) là đoạn đẹp trên dãy \(A^k\).

Input

• Dòng đầu chứa ba số nguyên dương \(n,k,d\) (\(n,k \le 10^5; d \le n \times k\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i \le 10^6\)).

Output

• Một dòng chứa một số nguyên là số chỉ số \(i\) cần đếm.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \times k \le 3 \times 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \times k \le 4 \times 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \times k \le 5 \times 10^7\).
• Subtask \(4\) (\(10\%\) số điểm): không có ràng buộc gì thêm.

Example

2 3 3
1 3

2

3 10 3
1 5 10

0

Biểu thức ngoặc là xâu chỉ gồm các kí tự (, ), [, ], {, }. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng \(0\).
• Nếu \(A\) là biểu thức ngoặc đúng và có bậc bằng \(k\) thì (\(A\)), [\(A\)], {\(A\)} cũng là một biểu thức ngoặc đúng và có bậc bằng \(k+1\).
• Nếu \(A\) và \(B\) là hai biểu thức ngoặc đúng và có bậc tương ứng là \(k_1\) và \(k_2\) thì \(AB\) cũng là một biểu thức ngoặc đúng là có bậc bằng \(max(k_1,k_2)\).

Ví dụ, ()[()] là một biểu thức ngoặc đúng có bậc bằng \(2\) còn {()[{}]} là một biểu thức ngoặc đúng có bậc bằng \(3\).

Với hai số nguyên \(n,k\), người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài \(n\) và bậc không vượt quá \(k\). Sắp xếp các biểu thực ngoặc theo thứ tự từ điển, chú ý rằng trong bài toán này thứ tự từ điển của các kí tự ngoặc là ( \(<\) ) \(<\) [ \(<\) ] \(<\) { \(<\) }.

Yêu cầu: Cho \(n,k\) và \(S\) là một xâu chỉ gồm các kí tự (, ), [, ], {, }, hãy tìm thứ tự của biểu thức ngoặc đúng \(S\).

Input

• Dòng đầu chứa hai số nguyên \(n,k\) (\(n \le 200, k \le 5\)).
• Dòng thứ hai chứa một xâu \(S\) độ dài \(n\).

Output

• Một dòng chứa một số nguyên là thứ tự của biểu thức ngoặc đúng.

Example

2 1
[]

2