Mẹ của Hùng đi công tác xa nên Hùng đi đóng tiền điện cho gia đình. Hùng băn khoăn không biết phải mang bao nhiêu tiền đi đóng trong khi Hùng biết chỉ số điện tiêu thụ trong tháng vừa qua của nhà mình.Em hãy viết chương trình giúp bạn Hùng tính tiền điện phải đóng của nhà mình biết giá 1 Kw/h xác định như sau nhằm khuyến khích dùng tiết kiệm điện:

Giá 1kw/h =\(\left\{{}\begin{matrix}\text{1000đ nếu chỉ số tiêu thụ < =100}\\\text{1500đ nếu 100< chỉ số tiêu thụ < =200}\\\text{2000đ nếu chỉ số tiêu thụ >200}\end{matrix}\right.\)

Bài 1: Viết chương trình tính tiền điện gồm các khoảng sau:

Tiền thuê bao điện kế: 1000đ/tháng

Định mức sử dụng điện cho mỗi hộ là: 50 KW với giá 230đ/KW

Nếu phần vượt định mức <= 50KW thì tính giá 480đ/KW

Nếu 50KW < phần vượt định mức < 100KW thì tính giá 700đ/KW

Nếu phần vượt định mức >= 100KW thì tính giá 900đ/KW

Chỉ số mới và cũ được nhập vào từ bàn phím

In ra màn hình chỉ số cũ, chỉ số mới, tiền trả định mức, tiền trả vượt định mức, tổng tiền

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 11 đến NN theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Input

Dòng đầu tiên chứa số lượng máy NN (1≤N≤25000)(1≤N≤25000).

Dòng thứ ii trong số N−1N−1 dòng tiếp theo chứa các khoảng cách từ máy ii đến máy i+1i+1 (i=1(i=1, 22, ..., N−1)N−1). Giả thiết rằng khoảng cách từ máy 11 đến máy NN không vượt quá 106106.

Output

Ghi ra độ dài của cáp nối cần sử dụng.

Sample Input

6
2
2
3
2
2

output:

7