Có ~n~ người xếp hàng mua vé một trận bóng theo thứ tự ~1~ đến ~n~. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_i~ là thời gian cần thiết để người thứ ~i~ mua vé cho mình. Nếu người thứ ~i+1~ rời hàng và nhờ người ~i~ mua hộ vé thì mất ~r_i~ thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 6*10^4)~
• Dòng thứ hai chứa ~n~ số nguyên dương miêu tả dãy ~t[1], t[2], ..., t[n]~.~(t[i] \le 30000)~
• Dòng thứ ba chứa ~n-1~ số nguyên dương miêu tả dãy ~r_[1], r_[2], ..., r_[n-1]~. ~(r[i] \le 30000)~

Output

• In ra thời gian ít nhất để mua vé cho ~n~ người.

Sample Test

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Trên dãy số nguyên ~a_1,a_2,...,a_n~ và với hai số nguyên ~w_1,w_2~, ta định nghĩa một bộ năm chỉ số ~1 \le i_1 < i_2 < ... < i_5 \le n~ được gọi là bộ năm và có trọng số được tính bằng: ~(w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_3 + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5})~.

Ví dụ, trên dãy gồm ~7~ số nguyên ~2,8,1,9,1,-1,8~ và ~w_1 = 1~, ~w_2 = -1~ thì bộ năm chỉ số ~2,3,4,6,7~ là một bộ năm có trọng số bằng ~(1 \times 8) + (-1 \times 1) + 9 + (-1 \times (-1)) + (1 \times 8) =25~, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số ~a_1,a_2,...,a_n~ và hai số nguyên ~w_1~ và ~w_2~. Hãy tìm bộ năm có trọng số lớn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,w_1,w_2~ ~(5 \le n \le 10^5; |w_1|, |w_2| \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(|a_i| \le 10^9)~.

Output

• Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100~
• Có ~20\%~ số test ứng với ~w_1 = w_2 = 0~
• Có ~20\%~ số test ứng với ~n \le 5000, w_1 = 0~
• Có ~20\%~ số test ứng với ~w_1 = 0~
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

7 1 -1
2 8 1 9 1 -1 8

Sample Output 1

25

Sample Input 2

7 0 0
2 8 1 9 1 -1 8

Sample Output 2

9

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tìm cách chia dãy ~a~ ra thành ít dãy con (không nhất thiết liên tiếp) nhất, sao cho các dãy con đều là dãy không giảm và mỗi phần tử của ~a~ thuộc đúng một dãy con.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 10^5)~

• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~. (~a_i \le 10^9~)

  Output

• In ra số lượng dãy con ít nhất thỏa mãn.

Sample Test

Input:

4
1 5 4 6

Output:

2

Hôm nay Kaku Seiga đến Nhân Thôn để đi ăn trộm. Có ~n~ ngôi nhà ở cạnh nhau. Số tiền trong ngôi nhà thứ ~i~ là ~a_i~. Cô sẽ không vào ~k~ nhà liên tiếp trở lên vì sẽ rất dễ bị phát hiện. Hãy cho cô biết cô sẽ lấy được số tiền lớn nhất là bao nhiêu?

Input:

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output:

• Số tiền lớn nhất Seiga có thể lấy được

Sample Test

Input:

6 3
6 10 10 13 10 10

Output:

40

Giải thích:

• Chọn các số 2 3 5 6.

Giới hạn:

• ~1 \le k \le n \le 10^5, 1 \le a_i \le 10^6~

Cho dãy ~a~ gồm ~n~ số nguyên dương. Bạn được chọn đúng ~k~ cặp số bằng các thao tác, mỗi thao tác có thể chọn một trong các cách sau:

• 1) Chọn ~2~ số đầu hàng.

• 2) Chọn ~2~ số cuối hàng.

• 3) Chọn ~1~ số đầu hàng và ~1~ số cuối hàng.

• 4) Loại ~1~ số đầu hàng ra khỏi hàng.

• 5) Loại ~1~ số cuối hàng ra khỏi hàng.

Sau mỗi thao tác, nếu bạn chọn thao tác ~1~, ~2~, ~3~ thì sẽ được cộng thêm số điểm bằng giá trị tuyệt đối của ~2~ số bạn chọn, đồng thời loại ~2~ số đó ra khỏi hàng và được tính là chọn 1 cặp số. Ngược lại với thao tác ~4~ và ~5~, bạn không được tính là chọn một cặp số.

Hãy tìm cách thực hiện đúng ~k~ thao tác để đem về số điểm là cao nhất. Biết ban đầu bạn có số điểm bằng 0.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~ ~(2*k \le n)~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a_i \le 10^9)~

Ouput

• In ra một số nguyên duy nhất là số điểm lớn nhất có thể thu về sau khi thực hiện đúng ~k~ thao tác.

Subtask

• Có 40% test thỏa mãn điều kiện: ~n \le 300~, ~k \le 2~.
• Có 40% test thỏa mãn điều kiện: ~n \le 30, 2*k = n~.
• Có 20% test thỏa mãn điều kiện: ~n \le 300~

Sample Test

Input

6 2
1 3 10 2 1 4

Output

12

Giải thích:

• Thao tác ~1~: Chọn ~2~ thẻ cuối hàng và được cộng ~|4-1| = 3~ điểm.
• Thao tác ~2~: Loại thẻ ở cuối hàng có giá trị bằng ~2~.
• Thao tác ~3~: Chọn một thẻ ở đầu hàng và một thẻ ở cuối hàng, thu được thêm ~|10-1| = 9~ điểm.
• Tổng cộng sẽ được ~2~ cặp số tương ứng ~12~ điểm.