Фома Дор хочет пригласить на вечеринку в далёкую-далёкую страну своих друзей. Всего у него n друзей, и каждый из них может приехать только в определённый промежуток дней с ai по bi. Разумеется, Фома Дор хотел бы видеть как можно больше гостей на своей вечеринке.
Машины в далёкой-далёкой стране очень странные и могут одновременно перевозить только ровно двух людей противоположного пола, то есть ровно одного мужчину и одну женщину. При этом страна настолько далёкая, что другого способа туда добраться не существует.
Фома Дор хочет выбрать какой-то день года и пригласить некоторых друзей, которые могут приехать в это время, так чтобы количество приглашённых мужчин равнялось количеству приглашённых женщин. Определите, сколько максимум гостей может быть на вечеринке.
Выходные данные
Выведите максимально возможное количество гостей на вечеринке Фомы Дора.
Примечание
В первом примере друзья 3 и 4 могут прийти в любой день между 117 и 128 включительно.
Во втором примере друзья с номерами 3, 4, 5 и 6 могут прийти в день 140.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
M 151 307
F 343 352
F 117 145
M 24 128
|
2
|
|
2
|
6
M 128 130
F 128 131
F 131 140
F 131 141
M 131 200
M 140 200
|
4
|