D. Дима и зайцы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Диме очень понравился подарок, который он получил от Инны. И еще больше — подарок, который он получил от Сережи.

На радостях Дима решил купить Инне n зайцев. Инна очень обрадовалась, выстроила зайцев в ряд, пронумеровала от единицы до n слева направо и начала кормить морковкой. Инна твердо решила покормить каждого зайца ровно один раз. Но вот в каком порядке их кормить?

Инна заметила, что каждый заяц излучает радость, когда его кормят. Причем радость конкретного зайца зависит от того, покормила ли Инна его соседей перед тем как покормить его. Инна знает, сколько радости излучит заяц, если на момент, когда Инна его кормит не покормлены соседние зайцы, покормлен один из соседних зайцев или покормлены оба. Обратите внимание, что у зайцев с номерами 1 и n нет левого и правого соседа соответственно, то есть у них никогда не могут быть покормлены оба соседа.

Помогите Инне максимизировать суммарную радость, которую излучат зайцы. :)

Входные данные

Первая строка входных данных содержит целое число n (1 ≤ n ≤ 3000) — количество зайцев. Далее следуют три строки по n целых чисел в каждой. В первой строке записаны числа a1 a2 ... an. Во второй строке — b1, b2, ..., bn. В третьей — c1, c2, ..., cn. Выполняются ограничения: 0 ≤ ai, bi, ci ≤ 105.

Число ai в первой строке обозначает радость, которую излучает заяц с номером i, если перед ним Инна не кормила его соседей. Число bi во второй строке обозначает радость, которую излучает заяц номер i, если перед ним Инна кормила ровно одного из его соседей. Число сi в третьей строке обозначает радость, которую излучает заяц номер i, если перед ним Инна кормила обоих его соседей.

Выходные данные

В единственной строке выведите максимально возможную суммарную радость зайцев, которую удастся достичь кормежкой Инне.

Примеры
Входные данные
4
1 2 3 4
4 3 2 1
0 1 1 0
Выходные данные
13
Входные данные
7
8 5 7 6 1 8 9
2 7 9 5 4 3 1
2 3 3 4 1 1 3
Выходные данные
44
Входные данные
3
1 1 1
1 2 1
1 1 1
Выходные данные
4