Американські гірки

Анна працює в парку розваг і займається проектуванням нового атракціону "Американські гірки". Атракціон складається з траси, по якій буде їздити спеціальний поїзд. Вважатимемо, що поїзд має нульову довжину. Анна вже спроектувала $n$ спеціальних секцій (зручно пронумерованих від $0$ до n - 1), які впливають на швидкість поїзда: підйоми, різкі гальмування тощо. Тепер вона повинна з'єднати їх шляхами, щоб отримати остаточний план атракціону.

Для кожного $i$ від $0$ до n - 1, включно, спеціальна секція $i$ характеризується двома значеннями:

• при в'їзді на цю секцію є обмеження швидкості: швидкість поїзда при в'їзді на секцію повинна бути меншою або дорівнювати s_i км/год,

• при виїзді з секції, швидкість поїзда стає рівно t_i км/год, незалежно від швидкості, з якою поїзд в'їхав на секцію.

В результаті план атракціону повинен являти собою єдину трасу, на якій у певному порядку зустрічаються всі $n$ спеціальних секцій. Кожна з $n$ секцій повинна увійти в остаточний план атракціону рівно один раз.

Між послідовними секціями повинні бути прокладені з'єднувальні шляхи. Анна повинна вирішити, в якому порядку розташувати секції вздовж траси атракціону, і вибрати довжину кожного з'єднувального шляху. Довжина кожного з'єднувального шляху вимірюється в метрах і повинна являти собою невід'ємне ціле число (можливо рівне нулю).

Кожен метр з'єднувального шляху між двома спеціальними секціями уповільнює поїзд на $1$ км/год. На початку поїздки поїзд в'їжджає на першу спеціальну секцію на трасі зі швидкістю $1$ км/год.

Остаточний план атракціону повинен відповідати наступним вимогам:

• поїзд не порушує обмеження на швидкість в'їзду на спеціальні секції;

• швидкість поїзда повинна бути строго позитивною в будь-який момент руху по трасі.

Вам потрібно вибрати порядок спеціальних секцій і довжини з'єднувальних шляхів між ними так, щоб наведені вимоги виконувалися, і сумарна довжина з'єднувальних шляхів була якомога меншою.