AT_abc298_g [ABC298G] Strawberry War

[problemUrl]: https://atcoder.jp/contests/abc298/tasks/abc298_g 長方形のケーキがあります。このケーキは $ H $ 行 $ W $ 列に並ぶ区画に分かれていて、上から $ i $ 行目、左から $ j $ 列目の区画にはイチゴが $ s_{i,j} $ 個載っています。 あなたは $ T $ 回の切断を行ってケーキを $ T+1 $ 切れに分割することにしました。各回の切断は、次のいずれかの方法で行います。 - 現存するケーキであって、区画の行の数が $ 2 $ 以上であるものを選ぶ。さらに、そのケーキから隣接する $ 2 $ 行を選び、その境界でケーキを切断してより小さなケーキ $ 2 $ 切れに分割する。 - 現存するケーキであって、区画の列の数が $ 2 $ 以上であるものを選ぶ。さらに、そのケーキから隣接する $ 2 $ 列を選び、その境界でケーキを切断してより小さなケーキ $ 2 $ 切れに分割する。 あなたの目標は、分割後のケーキに載ったイチゴの数をできるだけ均等にすることです。 分割後の $ T+1 $ 切れのケーキに載ったイチゴの個数を $ x_1,x_2,\ldots,x_{T+1} $ として、そのうち最大のものを $ M $、最小のものを $ m $ とするとき、$ M－m $ がとりうる最小値を求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ H,W\ \leq\ 6 $ - $ 1\ \leq\ T\ \leq\ HW-1 $ - $ 0\ \leq\ s_{i,j}\ \leq\ 10^{16} $ - 入力はすべて整数 ### Sample Explanation 1 下のように切り分けると左上のケーキに $ 2 $ 個、左下のケーキに $ 4 $ 個、中央のケーキに $ 4 $ 個、右上のケーキに $ 4 $ 個、右下のケーキに $ 3 $ 個のイチゴが載った状態になり、イチゴの個数の最大値と最小値の差は $ 4-2=2 $ となります。差をこれよりも小さくすることは出来ないため、$ 2 $ が答えとなります。 !\[\](https://img.atcoder.jp/abc298/6d6a4c5fc7ac2723af8e8b30e48957da.png)