{"code":"tracematrix","name":"[Python_Training] Vết của ma trận","description":"+ Cho ma trận $A$ có kích thước $n\\text { x }n$ với $n\\in \\mathbb{N}^{*}$\r\n\r\n + Vết của ma trận $A$ có kí hiệu là $tr(A)$ và được định nghĩa như sau: $tr(A)=\\sum\\limits_{i=1}^{n}A[i][i]$ (tổng các phần tử trên đường chéo chính).\r\n\r\nXét tất cả các ma trận vuông con (của ma trận $A$) có kích thước $k\\text{ x }k$ (bằng cách bỏ đi một số hàng( hoặc không bỏ hàng nào) và một số cột (hoặc không bỏ cột nào) của ma trận $A$ ) với $1\\le k\\le n$, hãy tìm ma trận con có vết lớn nhất và in giá trị đó ra màn hình.\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa hai số nguyên $n,k(1\\le n\\le 50;1\\le k\\le n)$\r\n\r\n+ $n$ dòng tiếp theo, mỗi dòng là một chuỗi gồm $n$ kí tự số ($'0'..'9'$)\r\n\r\n

Output

\r\n\r\n+ In ra kết quả thỏa mãn yêu cầu bài toán.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 3\r\n 123\r\n 456\r\n 789\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 15\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5 3\r\n 12689\r\n 55555\r\n 55555\r\n 55555\r\n 55555\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 16\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 2\r\n 233\r\n 111\r\n 233\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 6\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n **Giải thích:** Ở ví dụ 3, ta bỏ đi hàng $2$ và cột $1$. Ta sẽ còn lại ma trận con $2\\times 2$ có vết lớn nhất là $6$. Còn ở ví dụ $4$, ta bỏ đi các cột $1,2$ và các hàng $2,4$. Khi đó ta thu được ma trận $3\\times 3$ có vết lớn nhất là $9$\r\n\r\n!!! question \"Test 4\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5 3\r\n 23333\r\n 11111\r\n 23333\r\n 11111\r\n 23333\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 9\r\n ```\r\n \r\n ??? warning \"Note\"","points":550.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[34,36,37,14,28,38,39,18,17,29,23,27,35,25,26,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}