Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.
На складах фабрики находятся n колец, i-е кольцо имеет внутренний радиус ai, внешний радиус bi и высоту hi. Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:
- Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо j можно поставить на кольцо i только если bj ≤ bi.
- Кольца не должны проваливаться друг в друга, то есть кольцо j можно поставить на кольцо i только если bj > ai.
- Суммарная высота всех использованных колец должна быть максимальна.
Выходные данные
Выведите максимальную высоту башни, которую смогут получить работники фабрики.
Примечание
В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке 3, 2, 1.
Во втором примере можно либо поставить кольцо 3 на кольцо 4 и получить башню высоты 3, либо поставить кольцо 1 на кольцо 2 и получить башню высоты 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 5 1
2 6 2
3 7 3
|
6
|
|
2
|
4
1 2 1
1 3 3
4 6 2
5 7 1
|
4
|