AT_agc034_d [AGC034D] Manhattan Max Matching

[problemUrl]: https://atcoder.jp/contests/agc034/tasks/agc034_d すぬけくんは、二次元平面上に赤いボールと青いボールを置いて遊んでいます。 すぬけくんはまず、赤いボールを置く操作を $ N $ 回行いました。 $ i $ 回目の操作では、座標 $ (RX_i,RY_i) $ に $ RC_i $ 個の赤いボールを置きました。 すぬけくんは次に、青いボールを置く操作を $ N $ 回行いました。 $ i $ 回目の操作では、座標 $ (BX_i,BY_i) $ に $ BC_i $ 個の青いボールを置きました。 ここで、すぬけくんが置いた赤いボールの個数の総和と青いボールの個数の総和は等しいです。 つまり、$ \sum_{i=1}^{N}\ RC_i\ =\ \sum_{i=1}^{N}\ BC_i $ です。 以後、この値を $ S $ とおきます。 すぬけくんはこれから、赤いボールと青いボールのペアを $ S $ 個作ろうとしています。 どのボールも、ちょうど $ 1 $ つのペアに属するようにします。 ここで、座標 $ (rx,ry) $ にある赤いボールと座標 $ (bx,by) $ にある青いボールのペアのスコアを、 $ |rx-bx|\ +\ |ry-by| $ と定義します。 すぬけくんは、ペアのスコアの総和を最大化したいです。 すぬけくんのために、ペアのスコアの総和の最大値を求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 1000 $ - $ 0\ \leq\ RX_i,RY_i,BX_i,BY_i\ \leq\ 10^9 $ - $ 1\ \leq\ RC_i,BC_i\ \leq\ 10 $ - $ \sum_{i=1}^{N}\ RC_i\ =\ \sum_{i=1}^{N}\ BC_i $ - 入力される値はすべて整数である。 ### Sample Explanation 1 座標 $ (0,0) $ に置いてある赤いボールと座標 $ (2,2) $ に置いてある青いボールをペアにすると、 そのスコアは $ |0-2|\ +\ |0-2|=4 $ です。 また、座標 $ (3,2) $ に置いてある赤いボールと座標 $ (5,0) $ に置いてある青いボールをペアにすると、 そのスコアは $ |3-5|\ +\ |2-0|=4 $ です。 この $ 2 $ つのペアを作ると、スコアの総和は $ 8 $ になり、これが最大です。 ### Sample Explanation 2 同じ座標に複数回操作を行うこともあります。