Макс усердно готовится к самому важному мероприятию в жизни — финалу ACM ICPC. Он знает, что в ближайшее время будет проведено n соревнований по программированию, причём i-е из них начнётся в момент времени a_i, закончится в момент времени b_i и обладает полезностью c_i. Чтобы получше подготовиться, он хочет выбрать для участия такой набор соревнований, чтобы их суммарная полезность была максимальна, а при равенстве — чтобы их суммарная длительность была минимальна. Конечно же, Макс не может принимать участие одновременно в нескольких соревнованиях, а также никогда не начинает участие позже момента начала и никогда не бросает соревнование раньше его окончания.