問題文
すぬけくんは、二次元平面上に赤いボールと青いボールを置いて遊んでいます。
すぬけくんはまず、赤いボールを置く操作を N 回行いました。 i 回目の操作では、座標 (RXi,RYi) に RCi 個の赤いボールを置きました。 すぬけくんは次に、青いボールを置く操作を N 回行いました。 i 回目の操作では、座標 (BXi,BYi) に BCi 個の青いボールを置きました。 ここで、すぬけくんが置いた赤いボールの個数の総和と青いボールの個数の総和は等しいです。 つまり、sumi=1NRCi=sumi=1NBCi です。 以後、この値を S とおきます。
すぬけくんはこれから、赤いボールと青いボールのペアを S 個作ろうとしています。 どのボールも、ちょうど 1 つのペアに属するようにします。 ここで、座標 (rx,ry) にある赤いボールと座標 (bx,by) にある青いボールのペアのスコアを、 ∣rx−bx∣+∣ry−by∣ と定義します。
すぬけくんは、ペアのスコアの総和を最大化したいです。 すぬけくんのために、ペアのスコアの総和の最大値を求めてください。
制約
- 1leqNleq1000
- 0leqRXi,RYi,BXi,BYileq109
- 1leqRCi,BCileq10
- sumi=1NRCi=sumi=1NBCi
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
RX1 RY1 RC1
RX2 RY2 RC2
vdots
RXN RYN RCN
BX1 BY1 BC1
BX2 BY2 BC2
vdots
BXN BYN BCN
出力
ペアのスコアの総和の最大値を出力せよ。
入力例 1
出力例 1
座標 (0,0) に置いてある赤いボールと座標 (2,2) に置いてある青いボールをペアにすると、 そのスコアは ∣0−2∣+∣0−2∣=4 です。 また、座標 (3,2) に置いてある赤いボールと座標 (5,0) に置いてある青いボールをペアにすると、 そのスコアは ∣3−5∣+∣2−0∣=4 です。 この 2 つのペアを作ると、スコアの総和は 8 になり、これが最大です。
入力例 2
出力例 2
同じ座標に複数回操作を行うこともあります。
入力例 3
出力例 3