Одна телекоммуникационная компания планирует в скором будущем выпустить на рынок сразу два инновационных смартфона. Эти смартфоны будут называться «иннофон» и «иннофон плюс». Устройства уже полностью готовы к производству, и последняя задача, которую необходимо решить руководству компании, — выбрать оптимальную цену для каждого из смартфонов.

Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть $$$n$$$ потенциальных покупателей инновационных смартфонов. Для принятия решения $$$i$$$-й покупатель использует следующий алгоритм, характеризующийся двумя числами $$$a_i$$$ и $$$b_i$$$ ($$$a_i \geq b_i$$$):

• если цена на «иннофон плюс» не больше $$$a_i$$$, то он покупает «иннофон плюс»,
• иначе, если цена на «иннофон» не больше $$$b_i$$$, то он покупает «иннофон»,
• иначе он не покупает ничего.

Руководство компании хочет установить цены на «иннофон» и «иннофон плюс» таким образом, чтобы обе цены были целым числом, цена «иннофона» была не больше цены «иннофона плюс», и при этом суммарная стоимость проданных смартфонов была максимальна.

Требуется написать программу, которая находит максимально возможную суммарную стоимость проданных смартфонов.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 9 & n \le 100; b_i \le a_i \le 100 & 0 \\ \hline 2 & 10 & n \le 300 & 0, 1 \\ \hline 3 & 16 & n \le 3000 & 0, 1, 2 \\ \hline 4 & 11 & n \le 10^5; b_i = 0 & \\ \hline 5 & 16 & n \le 10^5; a_i = b_i & \\ \hline 6 & 7 & n \le 50\,000 & 0 - 3 \\ \hline 7 & 7 & n \le 75\,000 & 0 - 3, 6 \\ \hline 8 & 8 & n \le 100\,000 & 0 - 7 \\ \hline 9 & 8 & n \le 125\,000 & 0 - 8 \\ \hline 10 & 8 & n \le 150\,000 & 0 - 9 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.