У Роя и Бива есть множество из n точек на бесконечной числовой прямой.
Каждая точка имеет один из трех цветов: красный, зеленый или синий.
Рой и Бив хотят соединить все точки несколькими линиями. Линии могут быть проведены между любой парой данных точек. Стоимость линии равна расстоянию между точками, которые она соединяет.
Рой и Бив хотят провести линии так, чтобы они оба видели, что все точки соединены (напрямую или через несколько линий).
Однако, не все так просто: Рой не видит красный цвет, а Бив — синий.
Поэтому они хотят выбрать линии так, что если убрать все красные точки, то оставшиеся синие и зеленые точки будут соединены, и, аналогично, если убрать все синие точки, то оставшиеся красные и зеленые точки будут соединены.
Вычислите минимальную суммарную стоимость набора линий, который удовлетворяет вышеприведенным ограничениям.
Примечание
В первом тесте из условия оптимально нарисовать линии между точками (1,2), (1,4), (3,4). Их стоимости равны 4, 14, 5, соответственно.