Мальчик Лаврентий долго играл в свою любимую игру Nota и теперь сильно проголодался. Лаврентий хочет сделать себе бутерброды с колбасой и сыром, но для этого ему сначала нужно купить колбасу и сыр.
Город, в котором живет Лаврентий, небольшой. Дома в нем расположены в два ряда по n домов. В самом последнем доме второго ряда живет Лаврентий. Единственный магазин в городе для удобства расположен в первом доме первого ряда.
Между первым и вторым рядами проходит главный проспект города. Соседние дома одного ряда разделяют улицы.
На каждом переходе улицы или проспекта находится светофор. Чтобы перейти улицу, необходимо нажать кнопку на светофоре, подождать некоторое время, пока загорится зеленый свет, и перейти улицу. Время ожидания у разных светофоров может различаться.
У светофора на переходе от j-го дома i-ряда к (j + 1)-му дому того же ряда время ожидания равно aij (1 ≤ i ≤ 2, 1 ≤ j ≤ n - 1). У светофора на переходе от j-го дома одного ряда к j-му дому другого ряда время ожидания равно bj (1 ≤ j ≤ n). Других переходов в городе нет.
Лаврентий хочет дойти до магазина, купить продукты и вернуться назад. Главный проспект города — улица достаточно широкая, поэтому ее Лаврентий хочет перейти ровно один раз на пути в магазин и ровно один раз на пути обратно домой. Идти по одному и тому же пути Лаврентию будет скучно, поэтому он хочет, чтобы путь домой отличался от пути в магазин хотя бы в одном переходе.
Рисунок к первому примеру. Помогите Лаврентию определить наименьшее суммарное время, которое ему придется ждать на переходах.
В первой строке входных данных находится целое число n (2 ≤ n ≤ 50) — количество домов в каждом ряду.
В каждой из следующих двух строк через пробел находится n - 1 целое число — значения aij (1 ≤ aij ≤ 100).
В последней строке через пробел находятся n целых чисел bj (1 ≤ bj ≤ 100).
Выведите единственное целое число — наименьшее суммарное время, которое Лаврентию придется ждать на переходах, при условии, что он лишь единожды может переходить проспект как по дороге к магазину, так и по дороге назад.
4
1 2 3
3 2 1
3 2 2 3
12
3
1 2
3 3
2 1 3
11
2
1
1
1 1
4
Первый пример разобран на рисунке выше.
Во втором примере путь Лаврентия может выглядеть так:
В последнем примере Лаврентий посетит все переходы, поэтому ответ равен 4.
| Codeforces Round 325 (Div. 2) |
|---|
| Закончено |
