{"code":"ltbdgroup","name":"Chia nhóm (Trại hè MT&TN 2022)","description":"Có n học sinh tham giac một câu lạc bộ của trường đứng thành một hàng ngang, đánh số $1, 2, ..., n$ từ trái qua phải. Thầy giáo muốn chia $n$ bạn thành $m$ nhóm, mỗi nhóm là một dãy các bạn học sinh liên tiếp và tối thiểu phải có 1 bạn.\r\nVì các bạn học sinh đến từ nhiều lớp khác nhau nên không phải $a_i$ cũng quen biết $a_i$. Mức độ không quen biết của bạn học sinh $i$ và bạn học sinh $j$ được đặc trưng bởi số nguyên $a_{i,j}$. Mức độ không quen biết của một nhóm là nửa tổng mức độ không quen biết của các cặp học sinh bất kỳ trong nhóm (tính cả $a_{i,j}$ và $a_{j,i}$ và $a_{i,i}$).\r\n\r\n**Yêu cầu:** Hãy chia $n$ bạn học sinh thành $m$ nhóm sao cho tổng mức độ không quen biết của các nhóm là nhỏ nhất.\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa hai số nguyên dương $n, m (1 \\le n \\le 4000,1 \\le m \\le min(n, 800))$\r\n- $n$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên; số thứ $j$ trên dòng thứ $i$ là $a_{ij} (0 \\le a_{ij} \\le\r\n9, a_{ij} = a_{ji}, a_{ii} = 0)$\r\n\r\n

Output

\r\n\r\n- Một số nguyên duy nhất - tổng mức độ không quen biết nhỏ nhất của $m$ nhóm\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 2\r\n 0 2 0\r\n 2 0 3\r\n 0 3 0\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n ```","points":300.0,"partial":false,"time_limit":2.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}