input

5 5
1 1 3 2 8
1 5 5 2 9
3 1 2 4 6
2 3 3 2 9

output

5
27
16
14

可以Hack掉 @Fire_Storm 同学的题解。原因不明，似乎是边界条件有误。 @chen_zhe 请求增强数据