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à \(|h_i-h_j|\), 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 : \(h_1,h_2,...,h_N\) với \(1\le h_i\le 10^4\)

Output

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

Example

4
10 30 40 20

30

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\) hoặc ... hoặc \(i+K\) với chi phí là \(|h_i-h_j|\), 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 hai số nguyên \(N,K(2\le N\le 10^5,1\le K\le 100)\)

• Dòng thứ hai chứa \(N\) số nguyên : \(h_1,h_2,...,h_N\) với \(1\le h_i\le 10^4\)

Output

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

Example

5 3
10 30 40 50 20

30

Cho hai xâu \(s\) và \(t\) chỉ gồm các chữ cái thường \('a'..'z'\). Tìm xâu con chung dài nhất (subsequence) của hai xâu \(s\) và \(t\)

Input

• Dòng thứ nhất chứa xâu \(s(1\le |s|\le 3000)\)

• Dòng thứ hai chứa xâu \(t(1\le |t|\le 3000)\)

Output

• In ra xâu chung dài nhất cần tìm. Nếu có nhiều đáp án in ra bất kì !

Chú ý: Một xâu con của một xâu \(x\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(x\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Example

axyb
abyxb

axb

Cho một mảng số nguyên \(A\) có \(N\) phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm vị trí của hai phần tử khác nhau bất kỳ sao cho tổng của chúng có giá trị là \(X\). Nếu trong dãy \(A\) không tồn tại hai phần tử khác nhau có tổng là \(X\) thì in ra "No solution".

Input

• Dòng đầu chứa 2 số nguyên \(N\) và \(X\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_i\).

Output

• Hai vị trí \(i\) và \(j\) khác nhau sao cho tổng ở hai vị trí này có giá là \(X\). In vị trí phần tử nhỏ hơn trước phần tử lớn hơn.
• Nếu không tồn tại in ra "No solution".

Constants

• \(2 \leq N \leq 10^6\) và \(0 \leq A_i, X \leq 10^9\)

Example

6 16
2 3 5 7 9 12

4 5

Cho một dãy \(A\) gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Yêu cầu: Hãy tìm đoạn con \([l, r]\) \((1 \le l \le r \le n)\) gồm các phần tử liên tiếp \(A_l, A_{l+1}, \dots, A_{r-1}, A_r\) của dãy \(A\) sao cho tổng \(A_l + A_{l+1} + \dots + A_{r-1} + A_r\) là lớn nhất

Dữ liệu

Vào từ file văn bản MAXS.INP:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^5\) và \(|A_i|\le 10^9\).

Kết quả

Ghi vào file văn bản MAXS.OUT một số nguyên là tổng lớn nhất tìm được.

Ràng buộc

• Subtask 1: \(20\%\) số test ứng với \(1 \le N \le 100\)
• Subtask 2: \(20\%\) số test ứng với \(1 \le N \le 10^4\)
• Subtask 3: \(20\%\) số test ứng với \(A_i \ge 0\).
• Subtask 4: \(40\%\) số test không có ràng buộc gì thêm.

Ví dụ

6
2 -3 8 4 -5 3

12

Hiện nay, xem ý nghĩa biển số xe, số điện thoại, ngày sinh hay một dãy số nào đó là điều quan tâm của nhiều người. Cách đánh giá số đẹp của dãy số như sau: Tính tổng các chữ số trong dãy, nếu tổng là số có \(1\) chữ thì đó là giá trị số đẹp (độ đẹp của dãy số), ngược lại thì tiếp tục tính tổng các chữ số trong dãy.

Ví dụ:

• Dãy số ngày sinh \(02022020\) có tổng các chữ số là \(8\), vậy độ đẹp của dãy số là \(8\).
• Dãy số điện thoại \(0912345678\) có tổng các chữ số là \(45\), tính tục tính tổng ta được tổng là \(9\), vậy độ đẹp của dãy số là \(9\).

Yêu cầu: Cho dãy số có \(n\) chữ số. Hãy đánh giá độ đẹp của dãy số đã cho.

Input

• Chứa dãy số có \(n\) chữ số (\(n \leq 18\))

Output

• Một số nguyên là độ đẹp của dãy số.

Example

02022020

8

0912345678

9