Петя и Маша хорошие друзья. Этим вечером они решили включить телевизор. Петя предпочитает смотреть боевики. Маша - комедии. Каждый раз у них происходит битва за пульт, чтобы переключить канал у телевизора. Формально вам дано $$$n$$$ фильмов. Каждый фильм характеризуется временем начала и временем конца, а также у него есть тип:
Фильмы необязательно смотреть от начала до конца. Можно смотреть произвольные фрагменты и в любой момент переключаться между разными фильмами. Счастье каждого друга определяется как количество просмотренных им минут фильма его любимого жанра. Когда друзья смотрят фильм с типом $$$3$$$, то каждый из них счастлив в тот промежуток времени. Вам нужно определить суммарное максимальное счастье друзей при условии, что в каждый момент времени можно смотреть только один фильм.
Первая строка содержит число фильмов $$$n$$$ ($$$1 \le n \le 10^5$$$). В следующих $$$n$$$ строках задается $$$l_{i}$$$, $$$r_{i}$$$ ($$$1 \le l_{i} \lt r_{i} \le 10^9$$$), $$$t = 1, 2, 3$$$. Это время начала, окончания фильма и его жанр. В $$$l$$$ минуту фильм начинается и до начала $$$r$$$ минуты фильм заканчивается.
Выведите одно число — максимальную сумму счастья обоих друзей.
5 1 2 1 2 3 2 4 5 3 5 6 1 10 20 1
15
3 1 15 2 2 5 3 4 7 3
19
