Боб — утка. Он хочет попасть в гнездо Алисы, чтобы пойти с ней вместе понырять.
Утка — высшее животное! (Автор изображения — See Bang) Путешествие Боба может быть представлено в виде прямой линии, состоящей из \(n\) отрезков. Боб находится слева от первого отрезка, а гнездо Алисы — справа от последнего отрезка. Длина каждого отрезка дана в метрах. Каждый отрезок имеет один из трех типов: трава, вода или лава.
Боб может передвигаться тремя способами: плаванием, ходьбой и полетом. Он может переключаться между ними или менять свое направление в любой момент времени (даже если он находится в нецелой координате), и для этого не требуется дополнительное время. Боб может плавать только по воде, ходить только по траве и летать над любой местностью. Чтобы пролететь один метр, нужна \(1\) секунда. Чтобы проплыть один метр, нужно \(3\) секунды. И, чтобы пройти один метр, нужно \(5\) секунд.
У Боба конечное количество энергии. Плавание и ходьба расслабляют его, поэтому его количество энергии увеличивается на \(1\) за каждый метр, который он проходит или проплывает. С другой стороны, летать довольно утомительно, поэтому его количество энергии уменьшается на \(1\) за каждый метр полета. Пребывание на месте никак не влияет на его энергию. Конечно, количество энергии никогда не может становиться отрицательным. В начале количество энергии равно нулю.
За какое минимальное время Боб может достичь гнезда Алисы?
Выходные данные
Выведите одно целое число \(t\) — минимальное количество времени, которое нужно Бобу, чтобы добраться до гнезда Алисы.
Примечание
В первом примере Боб сначала проходит \(5\) метров за \(25\) секунд. После этого он пролетает оставшиеся \(5\) метров за \(5\) секунд.
Во втором примере Боб сначала проплывает \(10\) метров за \(30\) секунд. После этого он пролетает над лавой за \(10\) секунд.
В третьем примере водный пруд намного меньше. Боб сначала проплывает по нему за \(3\) секунды. Однако он пока что не может пролететь над лавой, так как у него только одна единица энергии, а ему нужно две. Поэтому он проплывет полметра назад, а потом вернется вперед. Это займет \(3\) секунды. Теперь у него есть \(2\) единицы энергии, значит он сможет пролететь лаву за \(2\) секунды.
В четвертом примере он будет ходить \(50\) секунд, летать \(10\) секунд, плавать \(15\) секунд и в конце летать \(5\) секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
10
G
|
30
|
|
2
|
2
10 10
WL
|
40
|
|
3
|
2
1 2
WL
|
8
|
|
4
|
3
10 10 10
GLW
|
80
|