Cho một dãy số nguyên gồm ~N~ phần tử ~a_1, a_2, …, a_N~. Một dãy con đơn điệu tăng của dãy trên là dãy ~a_{i_1}, a_{i_2}, …, a_{i_k}~ sao cho: ~i_1 < i_2 < … < i_k~ và ~a_{i_1} < a_{i_2} < … < a_{i_k}~. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Input

• Dòng đầu chứa số nguyên dương ~N~;
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, …, a_N~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

• ~1 ≤ n ≤ 1000, -10^9 ≤ a_i ≤ 10^9~

Output

• Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.

Sample

Input #1

6
1 2 5 4 6 2

Output #1

4

Hint

Giải thích #1:

• Dãy con tăng dài nhất là dãy ~1, 2, 4, 6~ độ dài dãy này là ~4~.

Problem source: Chuyên Sơn La Online Judge

Siro đã chế tạo ~1~ chú ếch máy có thể nhảy ~k~ bước với độ dài khác nhau ~(b_1, b_2, ..., b_k)~ trên đoạn đường thẳng. Siro đặt ếch trên đoạn đường thắng tại vạch xuất phát ~0~.

Bạn hãy cho Siro biết số cách nhảy để con ếch đến được điểm ~N~.

Input

Dòng đầu tiên ghi ~2~ số nguyên dương ~N (1 \le N \le 50)~ và ~k (1 \le k \le 10)~

Dòng thứ ~2~ ghi ~k~ số nguyên dương ~b_1, b_2, b_3, ..., b_k~

Output

Gồm ~1~ số nguyên dương duy nhất là số cách để con ếch đến được điểm ~N~ nói trên.

Sample

Input #1

8 2
2 3

Output #1

4

Hint

Ở #1, ta có các cách sau:

~(2, 2, 2, 2)~

~(2, 3, 3)~

~(3, 3, 2)~

~(3, 2, 3)~

Tổng cộng có ~4~ cách.

Có (N) hòn đá được đánh số (1,2,3,...,N). Với mỗi (i(1\le i\le N)), chiều cao của hòn đá thứ (i) là (h_i)

Có một con ếch ban đầu ở hòn đá (1). Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá (N).

Nếu con ếch đang ở hòn đá (i), thì nó có thể nhảy sang hòn đá thứ (i+1) hoặc (i+2) với chi phí là (|hi-hj|), trong đó (j) là vị trí nó muốn nhảy tới.

Tìm chi phí tối thiểu để nó đến được hòn đá thứ (N).

Input

• Dòng thứ nhất chứa số nguyên (N(2\le N\le 10^5))
• Dòng thứ hai chứa (N) số nguyên : (h1,h2,...,hN) với (1\le hi\le 10^4)

Output

• In ra chi phí tối thiểu cần tìm

Sample

Input #1

4
10 30 40 20

Output #1

30

Input #2

6
30 10 60 10 60 50

Output #2

40

Hint

Ở sample test 1, con ếch sẽ nhảy như sau: (1\rightarrow 2 \rightarrow 4), với chi phí là (|10-30|+|30-20|=30)

Problem source: DP Contest Atcoder

Đề đề xuất DHBB 2017 của THPT CHUYÊN BIÊN HÒA, T. HÀ NAM

Có ~n~ căn nhà cần sơn. Căn nhà ~i~ được sơn bằng một trong ~3~ màu Xanh, Hồng, Vàng với mức giá tương ứng là ~a_{i_1}, a_{i_2}, a_{i_3}~.

Yêu cầu: Tìm cách sơn màu cho ~n~ ngôi nhà sao cho hai căn nhà cạnh nhau không được sơn cùng màu và tổng chi phí sơn là ít nhất.

Input

• Dòng đầu chứa số nguyên dương ~N~ là số ngôi nhà;
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~a_{i_1}, a_{i_2}, a_{i_3}~ được ghi cách nhau bởi một dấu cách.

Giới hạn:

• ~1 ≤ N ≤ 10^5, 1 ≤ a_{i_1}, a_{i_2}, a_{i_3} ≤ 10^4~.

Output

• Một số nguyên duy nhất là chi phí ít nhất để sơn ~N~ ngôi nhà.

Sample

Input #1

4
13 23 12
77 36 64
44 89 76
31 78 45

Output #1

137

Hint

• Các ngôi nhà lần lượt được sơn các màu: Vàng, Hồng, Xanh, Vàng. Tổng chi phí là: ~12 + 36 + 44 + 45 = 137~

Problem source: Chuyên Sơn La Online Judge

Cho một bàn cờ hình chữ nhật gồm ~m~ hàng và ~n~ cột. Mỗi ô trên bàn cờ này có ghi một giá trị nguyên. Xuất phát từ ô ~(1, 1)~, bạn cần di chuyển đến ô ~(m, n)~. Ở mỗi bước, bạn được di chuyển sang phải một ô hoặc xuống dưới một ô. Hãy tìm cách di chuyển để tổng giá trị của các ô trên đường đi là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~m~ và ~n\ (1 ≤ m, n ≤500)~;
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên là giá trị các ô trên bàn cờ. Các ô này có giá trị tuyệt đối không quá ~10000~.

Output

• In ra tổng giá trị lớn nhất tìm được.

Sample

Input #1

5 5
-9 -1 -3 6 -6
8 -3 3 -7 2
4 -3 1 -10 -9
-4 -8 -2 -3 -10
-7 7 5 4 3

Output #1

11

Problem source: Kc97ble - Free Contest

Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome. Ví dụ: xâu bobseesanna có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:

• bobseesanna = bob + sees + anna
• bobseesanna = bob + s + ee + s + anna
• bobseesanna = b + o + b + sees + a + n + n + a.

Cho xâu ký tự, cần tìm cách biểu diễn xâudưới dạng một dãy gồm số ít nhất các palindrome. Ví dụ: cho s = bobseesanna, do ta có bobseesanna = bob + sees + anna và không thể biểu diễn bobseesanna bởi ít hơn là 3 palindrome nên biểu diễn này chính là biểu diễn cần tìm.

Input

• Gồm một dòng chứa xâu ký tự s chỉ gồm các chữ cái latin thường.

Output

• Gồm một dòng duy nhất ghi số lượng ít nhất các palindrome trong biểu diễn tìm được.Độ dài xâu s không quá 255 ký tự.

Sample

Input #1

bobseesanna

Output #1

3

Problem source: Chuyên Sơn La Online Judge