|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||25||13||12||52.174%|
There is a village along a road. This village has N houses numbered 1 to N in order along the road. Each house has a field that can make up to two units of the crop and needs just one unit of the crop. The total cost to distribute one unit of the crop to each house is the summation of carrying costs and growing costs.
Your task is to calculate the minimum total cost to supply one unit of the crop to each house.
The input consists of a single test case formatted as follows.
N d1 … dN−1 g1 … gN
The first line consists of an integer N (2 ≤ N ≤ 200,000), which is the number of the houses. The second line consists of N − 1 integers separated by spaces. The i-th integer di (1 ≤ di ≤ 109, 1 ≤ i ≤ N − 1) represents the carrying cost between the i-th and the (i+1)-th houses. The third line consists of N integers separated by spaces. The i-th integer gi (1 ≤ gi ≤ 109, 1 ≤ i ≤ N) represents the growing cost of the i-th house's field.
Print the minimum cost to supply one unit of the crop to each house.
2 3 1 5
3 100 100 1 2 3
4 1 2 3 1 1 100 100