AT_abc431_d [ABC431D] Robot Customize

There is a robot consisting of a head and a body. This robot has $ N $ types of parts that can be attached simultaneously: type $ 1, $ type $ 2,\ldots, $ type $ N $ . The weight of the type $ i\ (1\le i\le N) $ part is $ W _ i $ . Each part has a different **happiness** when attached to the head versus when attached to the body. The happiness when the type $ i\ (1\le i\le N) $ part is attached to the head is $ H _ i $ , and the happiness when attached to the body is $ B _ i $ . The robot falls over if the weight of the head is greater than the weight of the body. Here, the weight of the head and the weight of the body are the sums of the weights of the parts attached to the head or body, respectively. Takahashi wants to attach all $ N $ types of parts to the robot, one of each. Find the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.

The input is given from Standard Input in the following format: > $ N $ $ W _ 1 $ $ H _ 1 $ $ B _ 1 $ $ W _ 2 $ $ H _ 2 $ $ B _ 2 $ $ \vdots $ $ W _ N $ $ H _ N $ $ B _ N $

Print the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.

### Sample Explanation 1 By attaching type $ 1 $ and type $ 3 $ parts to the body and type $ 2 $ part to the head, the robot does not fall over and the sum of happiness can be made $ 217 $ . It is not possible to attach the parts without causing the robot to fall over and make the sum of happiness $ 218 $ or more, so print `217`. ### Sample Explanation 2 The robot will fall over if the only part is not attached to the body. Note that it is acceptable to attach no parts to the head. ### Sample Explanation 3 Note that the robot does not fall over if the head and body have equal weights. ### Sample Explanation 4 Note that the answer can exceed $ 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) $ - All input values are integers.