UOJ Logo Sharp Sword 剑锋 OI

SSOI

#20. 扑克阵法

统计

【问题描述】

    扑克阵法是扑克牌组成的N*N的大方阵,要解开这个阵法的要诀就是,拿走两个互不重叠的K*K的方阵中的扑克牌,使得这2*k^2张扑克牌的总分最大,从而使整个阵法失去主要能量而土崩瓦解。

【输入格式】

第1行两个数n,k。
第2行到第n+1行,每行n个非负整数,表示整个扑克阵法每张牌的分值。

【输出格式】

一个数,表示最大能拿走的总分。

【输入样例1】

4 2
1 1 1 1
8 8 1 1
8 8 9 9
1 1 9 9

【输出样例1】

68

【时空限制】

1S
512MB
对于20%的数据,1≤ k≤ n≤ 50
对于100%的数据,1≤ k≤ n≤ 1000
保证答案不超过2^31-1。