Cho một mảng ~n~ số nguyên ~a_i~ ~(0 \le a_i \le 1)~

Mỗi thao tác ta có thể gán ~a[i] = 1 - a[i]~

Yêu cầu: Số thao tác ít nhất để tạo được 1 mảng ~0, 1~ xen kẻ

Input

• Dòng đầu tiên là số nguyên ~n~
• Dòng tiếp theo là ~n~ số nguyên ~a_i~

Output

Yêu câu của bài toán

Giới hạn

• ~20~% số điểm có ~1 \le n \le 200~
• ~80~% số điểm có ~1 \le n \le 10000~

Ví dụ

Sample input

3
0 0 0

Sample output

1

Giải thích ví dụ

0 1 0

Một tam giác gọi là tam giác gần Perfect nếu tam giác đó là một tam giác cân có 3 cạnh nguyên dương ~(a, a, b)~, ~|a - b| = 1~ và có diện tích là số nguyên dương.

Yêu cầu: Cho một số nguyên dương ~n~, tính tổng chu vi của tất cả các tam giác gần Perfect có chu vi bé hơn hoặc bằng n

Input

• 1 dòng duy nhất là số nguyên ~n~

Output

Yêu câu của bài toán

Giới hạn

• ~100~% số điểm có ~1 \le n \le 10^7~

Ví dụ

Sample input

16

Sample output

16

Giải thích ví dụ

Chỉ có duy nhất 1 tam giác Perfect là ~(5, 5, 6)~ có tổng chu vi là 16

Bạn đang cầm yasuo. Có ~n~ con creep. Con creep thứ ~i~ đứng ở vị trí ~a_i~, bạn phải giết hết ~n~ con creep này. Đồng thời bạn cũng có ~m~ skin yasuo, skin thứ ~i~ có phạm vi tấn công là ~b_i~ và tốn ~c_i~ mana, mỗi lần tấn công chỉ tiêu diệt được 1 con creep. Biết rằng yasuo này bị què nên luôn ở vị trí 0.

Yêu cầu: Tìm cách tiêu diệt kẻ thù sao cho lượng mana tiêu thụ là ít nhất, nếu không thể tiêu diệt hết, hãy in ra "Bo da mat Le Thu".

Input

• Dòng đầu tiên là 2 số nguyên ~n~ và ~m~ ~(n, m \le 10^5)~
• Dòng thứ 2 là ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~
• ~m~ dòng tiếp theo mỗi dòng là ~2~ số nguyên ~b_i~ và ~c_i~ tương ứng với skin thứ ~i~ ~(1 \le b_i, c_i \le 10^9)~

Output

Yêu cầu của bài

Giới hạn

• ~40~% số điểm có giới hạn ~n, m \le 10^3~
• ~60~% số điểm không có giới hạn gì thêm

Ví dụ

Sample input

4 2
1 2 3 4 
5 5
3 1

Sample output

8

Giải thích ví dụ

Dùng skin thứ ~2~ ba lần để tiêu diệt con creep thứ ~1, 2, 3~, dùng skin thứ nhất ~1~ lần để tiêu diệt con creep thứ ~4~

Cho một bảng ~n~ x ~m~ kí tự ~E,W,S,N~ tương ứng với Đông, Tây, Nam, Bắc. Robot nằm trên ô có kí tự ~E~ thì qua phải, nằm trên ô có kí tự ~W~ thì qua trái, ~S~ thì đi xuống, ~N~ thì đi lên.

Yêu cầu: Số vị trí trên bảng sao cho robot không thể đi ra khỏi bảng

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n, m~
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ kí tự ~E, W, S, N~ ~(n, m \le 10^3)~

Output

Yêu câu của bài toán

Giới hạn

• Không giới hạn gì thêm

Ví dụ

Sample input

6 5
WSWNS
NSWEW
EESNS
ESENE
WWNEN
EENEN

Sample output

17