Cho dãy ~a~ gồm ~n~ phần tử nguyên dương. Hãy đếm số tổng khác nhau có thể tạo ra từ các dãy con của ~a~ (không tính dãy rỗng).

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.

Output

• Gồm một số nguyên dương miêu tả kết quả bài toán.

Constraints

• ~1 \le n \le 1000~
• ~0 < a_i \le 1000~.

Input

3
1 4 5

Output

6

Subtasks

• Subtask ~1~: ~n \le 20~ ~(30\%)~
• Subtask ~2~: ~n \le 50~ ~(40\%)~
• Subtask ~3~: Không có ràng buộc gì thêm ~(30\%)~

Một nhóm kỹ sư tại trung tâm điều khiển Robot đang thiết kế một chuỗi lệnh điều khiển. Mỗi chuỗi lệnh phải tuân theo một cấu trúc an toàn để robot không bị lỗi khi thực thi. Cấu trúc an toàn này có thể được biểu diễn bằng một biểu thức lệnh đúng, được định nghĩa như sau:

Một chuỗi lệnh rỗng là biểu thức đúng.

Nếu ~A~ là biểu thức đúng, thì ~⟨A⟩~) cũng là biểu thức đúng.

Nếu ~A~ và ~B~ là biểu thức đúng, thì ~AB~ cũng là biểu thức đúng.

Robot có một bảng điều khiển gồm ~n~ vị trí (đánh số từ ~1~ đến ~n~), mỗi vị trí tương ứng với một nút có thể lập trình một phần của biểu thức lệnh.

Tại mỗi vị trí ~i~, kỹ sư có thể:

• Gán nút đó là một lệnh mở ~(~, và tăng độ ổn định ~s~ lên ~a_i~.

• Gán nút đó là một lệnh đóng ~)~, và giảm ~s~ đi ~a_i~.

• Bỏ qua vị trí này (không đặt gì).

Sau khi hoàn tất lựa chọn, ta tạo ra chuỗi lệnh bằng cách nối các ký tự đã được chọn từ trái sang phải, chỉ gồm các dấu ~(~ hoặc ~)~, và nó phải tạo thành một biểu thức đúng như định nghĩa ở trên.

Nhiệm vụ của bạn là chọn các vị trí sao cho chuỗi lệnh tạo ra là một biểu thức đúng, và giá trị ~s~ thu được là lớn nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n ( |a_i| \le 10^9)~

Output

• In ra một số nguyên duy nhất là giá trị ~s~ lớn nhất có thể chọn được.

Test mẫu

Input

4
0 -5 1 2

Output

5

Input

9
5 -2 2 3 -4 -4 -1 -2 9

Output

21

Subtask

• Subtask 1 ~(25\%)~: ~n \le 10~.
• Subtask 2 ~(25\%)~: ~n \le 10^3~.
• Subtask 3 ~(25\%)~: ~n \le 10^5~ và không có quá ~10^3~ giá trị ~a_i~ khác ~0~.
• Subtask 4 ~(25\%)~: ~n \le 10^5~.

Hai nhà thám hiểm đang bị chia cắt trong một miệng núi lửa rộng lớn đã bị đóng băng trong suốt mùa đông. Miệng núi lửa có dạng hình chữ nhật gồm ~n~ hàng và ~m~ cột, mỗi ô trong bản đồ có thể là:

• Đá băng (không thể đi qua),
• Đất mềm (có thể đi qua),
• hoặc vị trí của một nhà thám hiểm.

Với sự ấm lên toàn cầu, mỗi ngày trôi qua, các khối đá băng tiếp giáp với đất mềm (ở bốn hướng: trên, dưới, trái, phải) sẽ tan ra, biến thành đất mềm mà thám hiểm gia có thể bước vào.

Hai nhà thám hiểm chỉ có thể di chuyển qua các ô đất mềm, và họ muốn tìm đường đến với nhau càng sớm càng tốt.

Yêu cầu: Hãy xác định số ngày ít nhất cần thiết để hai nhà thám hiểm có thể gặp nhau.

Input

Dòng đầu tiên có 2 số nguyên ~n, m~

~n~ dòng tiếp theo, mỗi dòng có ~m~ kí tự mô tả bản đồ vào thời điểm bắt đầu: '.' thể hiện 1 ô đất mềm, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện vị trí nhà thám hiểm. Có chính xác 2 ô chữ L.

Output

In ra một số nguyên là số ngày ít nhất mà 2 nhà thám hiểm có thể gặp nhau

Test mẫu

Input

10 10
LXXXXXXXXX
XX.X...XXX
XXX.X.X.XX
XX.X.X.X.X
X..X.X.X.X
X.XXX.X..X
X.X.X.X.XX
X.X...X.XX
XX.X.XXX.X
XXXXXXXXLX

Output

2

Giải thích

Bản đồ của ngày 1

LX.X...XXX
X.......XX
XX.......X
X.........
..........
..........
.........X
.........X
X.....X...
XX.X.XXXLX

Bản đồ của ngày 2

L..X....XX
.........X
X.........
..........
..........
..........
..........
..........
..........
X.....X.L.

Subtask

• Subtask 1 ~(100\%)~: ~n, m <= 1500~

Trong một lễ hội truyền thống ở làng Kappa, Nitori Kawashiro được giao nhiệm vụ thiết kế một lá cờ hiệu dài để treo dọc trên con phố chính.

Lá cờ được mô tả như một lưới có kích thước ~n~ dòng và ~m~ cột. Mỗi ô trên cờ có thể là:

Ký tự #: đại diện cho vải màu đen.

Ký tự .: đại diện cho vải màu trắng.

Tuy nhiên, để phù hợp với thẩm mỹ truyền thống, các cột liên tiếp trên lá cờ cần tuân thủ quy tắc:

Mỗi đoạn các cột cùng màu (toàn # hoặc toàn .) phải có độ dài ít nhất là ~x~ cột và nhiều nhất là ~y~ cột.

Do một sự cố trong khâu sản xuất, lá cờ đã bị làm sai. Để tiết kiệm chi phí, Nitori muốn sửa đổi ít ký tự nhất trên lá cờ để nó đáp ứng yêu cầu về màu sắc và độ dài đoạn cột cùng màu như trên.

Yêu cầu: Hãy giúp Nitori tính ra số ký tự ít nhất cần thay đổi để lá cờ trở nên hợp lệ.

Input

Dòng đầu tiên chứa bốn số nguyên dương ~n, m, x, y~ lần lượt là số dòng, số cột, số cột cùng màu tối thiểu, và số cột cùng màu tối đa.

~n~ dòng tiếp theo, mỗi dòng gồm ~m~ ký tự # hoặc . — mô tả trạng thái ban đầu của lá cờ.

Output

Gồm một số nguyên là số lượng ký tự ít nhất cần sửa để lá cờ hợp lệ.

Test mẫu

Input

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

Output

11

Subtask

Subtask 1 ~(100\%)~: ~1 ≤ n, m, x, y ≤ 1000~

Megumin đang chiến đấu ở trên một bãi quái vật. Bãi quái gốm ~N~ con quái vật, con quái thứ ~i~ có lượng máu là ~H_i~. Megumin có 2 kĩ năng như sau:

• Burn: Megumin niệm chiêu lên 1 con quái ~i~ bất kỳ, gây 1 sát thương cho con quái này. Kĩ năng này tiêu hao 1 MP.
• Explosion: Megumin niệm chiêu lên 1 con quái ~i~ bất kỳ, gây ~X~ sát thương cho con quái này.
  • Nếu con quái có ~H(i) > X~ máu, nó sẽ mất ~X~ máu
  • Nếu con quái có ~H(i) <= X~ máu, nó sẽ chết với một vụ nổ, gây ~H(i) - 1~ sát thương cho những con quái cạnh nó (con quái thứ ~i-1~ và ~i+1~). Nếu vụ nổ đủ sát thương để hạ gục con quái thứ ~i - 1~ hay ~i + 1~ thì nó sẽ tiếp tục phát nổ gây ~H(i - 1) - 1~ hoặc ~H(i + 1) - 1~ sát thương lên những con quái tiếp theo cho đến khi hết quái lân cận hoặc có quái đỡ được sát thương vụ nổ.
• Kĩ năng này tiêu tốn ~X~ MP và sau khi dùng kĩ năng này thì cô không thể dùng thêm kĩ năng được nữa.

Megumin muốn tiêu diệt bãi quái này một cách gọn gàng và đơn giản, do đó cô nhờ bạn tính xem lượng MP thấp nhất mà cô cần dùng để tiêu diệt hết bãi quái này là bao nhiêu

Ràng buộc

~N <= 10~⁵

~1 <= H~_i ~<= 10~⁹

Input

Gốm 2 dòng:

• Dòng 1: chứa số nguyên ~N~, số lượng quái có trong bãi quái vật
• Dòng 2: chứa ~N~ số nguyên, lượng máu tương ứng của mỗi con quái vật

Output

Gồm 1 số nguyên duy nhất là kết quả của bài toán

Sample

• Input

3
1 1 1

• Output

3

Note

Megumin sử dụng Burn vào mỗi con quái 1 lần

• Input

9  
1 2 3 2 2 2 3 2 1

• Output 12

• Note Megumin sử dụng Burn vào 5 con quái cuối cùng lần lượt 1, 2, 3, 2, 1 lần sau đó sử dụng Explosion vào con quái thứ 3 với 3 MP

Subtask

Sub 1: ~N <= 1000~ (40%)

Sub 2: Điều kiện mặc định của đề bài (60%)