AT_abc431_d [ABC431D] Robot Customize

頭と体からなるロボットがあります。 このロボットには、同時に取り付けられる部品が種類 $ 1, $ 種類 $ 2,\ldots, $ 種類 $ N $ の $ N $ 種類あります。 種類 $ i\ (1\le i\le N) $ の部品の重さは $ W _ i $ です。 それぞれの部品には、頭に取り付けたときと体に取り付けたときで異なる**嬉しさ**があります。 種類 $ i\ (1\le i\le N) $ の部品を頭に取り付けたときの嬉しさは $ H _ i $ 、体に取り付けたときの嬉しさは $ B _ i $ です。 ロボットは頭の重さが体の重さより大きいと倒れてしまいます。 ここで、頭の重さおよび体の重さはそれぞれ頭もしくは体に取り付けられた部品の重さの合計とします。 高橋くんは、 $ N $ 種類の部品をすべて $ 1 $ 個ずつロボットに取り付けたいと思っています。 ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ W _ 1 $ $ H _ 1 $ $ B _ 1 $ $ W _ 2 $ $ H _ 2 $ $ B _ 2 $ $ \vdots $ $ W _ N $ $ H _ N $ $ B _ N $

ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を出力せよ。

### Sample Explanation 1 種類 $ 1 $ と種類 $ 3 $ の部品を体に、種類 $ 2 $ の部品を頭に取り付けることで、ロボットを倒さないようにしつつ嬉しさの合計を $ 217 $ にすることができます。 ロボットを倒さないように部品を取り付けて嬉しさの合計を $ 218 $ 以上にすることはできないため、`217` を出力してください。 ### Sample Explanation 2 唯一の部品を体に取り付けないとロボットは倒れてしまいます。 頭にひとつも部品を取り付けなくてもよいことに注意してください。 ### Sample Explanation 3 頭の重さと体の重さが等しい場合、ロボットは倒れないことに注意してください。 ### Sample Explanation 4 答えが $ 2 ^ {32} $ を超える場合があることに注意してください。 ### Constraints - $ 1\le N\le500 $ - $ 1\le W _ i\le500\ (1\le i\le N) $ - $ 1\le H _ i\le10 ^ 9\ (1\le i\le N) $ - $ 1\le B _ i\le10 ^ 9\ (1\le i\le N) $ - 入力はすべて整数