Một ngày lướt fb, TN thấy một đôi couple chia sẻ bài bói toán online, rằng đôi couple kia hợp nhau thế nào, yêu nhau ra sao, vân vân và mây mây. Tò mò không biết âm dương ngũ hành, yêu nhau hợp tình nghĩa không, TN cũng bảo Ami cùng mình tham gia bói toán online. Nhưng Ami đời nào tin những thuật toán tào lao ấy? “Bởi vì không một thuật toán nào định nghĩa được tình yêu cả” – Ami nói. Cậu bèn dẫn TN đến cặp thầy bói nổi danh thiên hạ - zerolifes và huy_yeu_minh_nghia. Hai lúc nào cũng hơn một mà :)).

Sau khi xem chỉ tay, tướng số, ngũ hành, chiêm tinh, zerolifes không nói không rằng. Anh đọc liên tục 1 câu thần chú chỉ toàn những con số vô nghĩa nhưng không giảm. Đột nhiên zerolife dừng lại, huy_yeu_minh_nghia hét lên một số :”30”. “Nhưng 30 là gì ? Không lẽ 2 vị này cao thâm đến mức biết ngày mình và TN quen nhau sao ?”, Ami thầm nghĩ, “Hay 30 là số tỉ USD mà sau này mình tậu được ? Không, không thể ít như vậy được.” Không thể kìm nén, Ami thỉnh cầu 2 vị cao nhân. Zerolifes nói :”Đơn giản thôi, âm dương hòa hợp, trong cương có nhu, trong nhu có cương, cậu hãy ghi nhớ dãy số của ta và số mà huy_yeu_minh_nghia vừa đọc, hãy đếm xem trong dãy số của ta có bao nhiêu cặp số có tổng đúng bằng k. Nếu số cặp càng lớn, khả năng hai người bền lâu càng nhiều.” Tất nhiên, Ami không dám làm ngay lập tức, vì sợ sự thật có thể làm cậu suy sụp.

Tóm lại, có một dãy gồm \(n\) số nguyên dương không giảm \(a_1,\) \(a_2,\) \(a_3,\) \(…,\) \(a_n\) và một số \(k,\) Ami muốn đếm số cặp \((i,\) \(j)\) không trùng nhau mà \(a_i\) \(+\) \(a_j\) \(=\) \(k,\) lưu ý rằng \((i,\) \(j)\) và \((j,\) \(i)\) được tính là \(1\) cặp.

Input

• Dòng đầu gồm \(2\) số nguyên dương \(n\) và \(k\) \((n\) \(\leq\) \(10^6,\) \(k\) \(\leq\) \(10^9).\)
• Dòng thứ hai gồm \(n\) số nguyên dương không giảm \(a_1,\) \(a_2,\) \(a_3,\) \(…,\) \(a_n\) \((a_i\) \(\leq\) \(10^9).\)

Output

• Hãy in ra một số nguyên là kết quá của bài toán.

Example

4 6
1 1 5 5

4

6 5
1 1 1 4 5 5

3

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^9)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^3)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90

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 một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1 < i_2 < \cdots < i_k\) và \(A[i_1] < A[i_2] < \cdots < A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Input

• Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
• Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Output

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

Example

6
1 2 5 4 6 2 

4