CF777E Hanoi Factory

Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings. There are $ n $ rings in factory's stock. The $ i $ -th ring has inner radius $ a_{i} $ , outer radius $ b_{i} $ and height $ h_{i} $ . The goal is to select some subset of rings and arrange them such that the following conditions are satisfied: - Outer radiuses form a non-increasing sequence, i.e. one can put the $ j $ -th ring on the $ i $ -th ring only if $ b_{j}a_{i} $ . - The total height of all rings used should be maximum possible.

N/A

N/A

In the first sample, the optimal solution is to take all the rings and put them on each other in order $ 3 $ , $ 2 $ , $ 1 $ . In the second sample, one can put the ring $ 3 $ on the ring $ 4 $ and get the tower of height $ 3 $ , or put the ring $ 1 $ on the ring $ 2 $ and get the tower of height $ 4 $ .