まず最初に下半分の \(N \times N\) 領域に注目する． この正方形領域内でできるだけ総和が大きくなるように数を書き込んで良いことが証明できる．

そのような書き込み方は複数通り存在するが，上半分の \(N \times N\) の様子に関わらず，下半分での最適な数の書き込み方というものが決定できる．

これは次のように考えるとわかる． 下半分に値を書き込み終わったあと，残った列容量が \(b_1,\cdots,b_N\) だったとする． もしある \((i,j)\) が存在して，\(b_i \geq b_j+2\) であり，かつ下半分のフローを組み替えて \(b_i-1,b_j+1\) に変更することができるなら，この操作を行ったほうがよい． この操作を可能な限り行ったあとの \(b\) は，多重集合として一意に決定される． （列容量 \(u \to u-1\) にする際のコストを \(-u\) とした最小費用流を考えるとわかる．）

上半分の問題は mincut を考えると解けるので，下半分の最適なフローを求める問題だけが残った．

以降は盤面の下半分だけに注目し，行番号を \(1\) から \(N\) と置き直して議論する．

まずは，すべての列が \(B_i\) を流しきることができる条件というものを考える． \(A_1 \geq \cdots \geq A_N\) とソートされていることを仮定する． maxflow の代わりに mincut を考えると，次のような理解が可能になる．

各列 \(i\) に対して，\(B_i\) 個の石を用意する． その後，\(i\) 列目の行 \(1,\cdots,N\) のマスに対し，この順に，\(Y_i\) 個ずつの石を置いていく． 途中で石が足りなくなったらそこで終わる． 例えば，最後は \(B_i \bmod Y_i\) 個の石を置いて終わる． 最後の行まで行って石が余ったらそれは捨てる． その後，各行 \(1,\cdots,N\) について，行番号がそれ以下のマス(列番号は問わない)から \(A_i\) 個の石を取っていく． これで取れた石の個数がフローの流量となる．

このやり方をもとに，最適な \(b_i\) を求めていく． これは，辺容量に関する分割統治で解ける． まず，各列について，最終的な \(b_i\) の値の範囲が \([0,2L]\) とわかっている状態から始める． 各 \(i\) について，\(b_i \leq L\) か \(b_i \geq L\) かを決定する（\(b_i=L\) だったらどちらにも分類されうる）ことを考える． そのために，各列容量を \(v_i=\max(B_i-L,0)\) にした場合のフローの様子を考える必要がある．

列容量を \(v_i\) にした状態で，各行に置かれる石の個数を \(z_i\) とおく． ここで，\((z_i-A_i)\) の prefix sum を \(w_0,\cdots,w_N\) とおく．

\(w_i\) が min を達成する \(i\)（複数あるなら最小のもの）を \(q\) とおく． 各列 \(i\) について，\(i\) 列目で \(v_i\) 個目に置いた石の行番号を \(r_i\) とおく． \(r_i \leq q\) である場合，\(v_i\) 個目の石を除くと，フローの容量が減る． つまり，\(i\) 列目から流れるフローは \(v_i\) 以上であることがわかる． 逆に \(q < r_i\) である場合，\(v_i+1\) 個目の石を置いても，フローの容量は増えない． よって \(i\) 列目から流れるフローは \(v_i\) 以下であることがわかる．

これで，各列について，\(b_i \leq L\) or \(b_i \geq L\) かを判別することができた． ただしこのまま再帰を潜ろうとすると，それぞれで \(N\) 行見て \(w_i\) を計算しなくてはならないため，まだ計算量が悪い．

そこでまず，各列容量が \(v_i\) だと思った上で行番号 \(q\) 以下のところに石をすべて置き，そして行と貪欲にマッチさせて消費することにする． すると石は残らず，行番号 \(q\) 以下の行容量が変化することになる． ここで， \(r_i \leq q\) の \(i\) に関して考えるときは，\(q<r_j\) を満たす列 \(j\) と，行番号が \(q\) より大きい部分は考慮する必要がなくなっている． 同様に，\(q< r_i\) について考えるときは，\(r_j \leq q\) を満たす列 \(j\) と，行番号が \(q\) 以下の部分については考慮する必要がない．

これで，見るべき行の区間も \(2\) つに分けることができた． あとはこれにそって分割統治を実装すればよい．

計算量は全体で \(O(N \log N + N \log \max(Value))\)

回答例(C++)