N (1 <= N <= 1 000 000) people wait on ticket queue. The time for which i-th person will buy ticket is Ti, i = 1, 2, ..., N. Two neighbors can buy tickets together i-th and (i + 1) and the time is Si, i = 1, 2, ..., N - 1. Find the minimal amount of time for which, every person in the queue will buy ticket.
Input:
T = [5, 2, 7, 8, 3, 9, 4, 2]
S = [6, 3, 10, 12, 8, 8, 6]
Output:
29