Sau kì nghỉ, bạn An có ~N~ món quà được đánh số từ ~1~ đến ~N~, món quà thứ ~i~ có giá trị là ~i~. An muốn gói quà để chia cho các em của mình, mỗi gói quà có đúng hai món quà và giá trị gói quà là tổng giá trị của hai món quà trong gói quà đó.

Yêu cầu

Hãy cho biết An có thể có nhiều nhất bao nhiêu gói quà mà giá trị mỗi gói quà là ~K~.

Dữ liệu đầu vào

Gồm hai số nguyên dương ~N~ và ~K~ ~(1 \le N, K \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số gói quà thỏa mãn yêu cầu.

Ví dụ

Ví dụ 1

INPUT

8 5

OUTPUT

2

An yêu thích lập trình. An muốn tạo dữ liệu cho một trò chơi đố chữ của mình. Với một xâu kí tự ~S~, An muốn tìm ra thông tin: số ~T~ và xâu kí tự ~SS~ tương ứng của ~S~ thỏa mãn:

• ~T~ là tổng số lần xuất hiện của các kí tự trong ~S~ mà số lần xuất hiện lớn hơn ~1~.
• ~SS~ chứa các kí tự có trong ~S~ (giữ nguyên thứ tự xuất hiện và kí tự nào xuất hiện nhiều sẽ giữ lại một kí tự tương ứng).
• ~T~ và ~SS~ chỉ xác định dựa theo các kí tự chữ cái tiếng Anh (không phân biệt chữ hoa, chữ thường).

Yêu cầu

Cho biết xâu ~S~. Hãy xác định ~T~ và ~SS~ giúp bạn An?

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa xâu ~S~ (không quá ~10^5~ kí tự).

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng 1: chứa số ~T~.
• Dòng 2: chứa xâu ~SS~.

Ví dụ

Ví dụ 1

INPUT

Tro choooi

OUTPUT

4
trochi

An học giỏi môn Tin học do tham gia học trên một trang Web học lập trình trực tuyến WW. Điểm kĩ năng của An đang được ghi nhận trên WW là ~C~. Hiện đang có một đợt thi trên WW, đợt thi có ~N~ bài tập được đánh số từ ~1~ đến ~N~; nếu An làm được bài ~i~ thì điểm kĩ năng được tự động tăng thêm ~T_i~ (chỉ tăng cho lần làm đúng đầu tiên bài đó). An dự kiến là làm được bài ~i~ nếu điểm kĩ năng của An (trước khi chọn làm bài ~i~) không nhỏ hơn ~D_i~. An có thể chọn bài nào làm trước đều được.

Yêu cầu

Cho biết điểm kĩ năng của An trước đợt thi là ~C~, các giá trị ~T_i~ và ~D_i~ của bài tập ~i~. Hãy xác định điểm kĩ năng của An đạt được sau đợt thi (theo dự kiến của An).

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa hai số ~C~ và ~N~ ~(1 \le C, N \le 10^6)~.
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo, chứa hai số ~T_i~ và ~D_i~ ~(1 \le T_i, D_i \le 10^3)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là điểm kĩ năng của An theo yêu cầu.

Ví dụ

Ví dụ 1

INPUT

100 3
100 200
20 50
50 110

OUTPUT

170

An biết một cửa hàng bánh nổi tiếng vừa tung ra một chương trình khuyến mãi đặc biệt. Mỗi ngày, cửa hàng sẽ xếp ~N~ chiếc bánh theo một hàng hàng dài đánh số từ ~1~ đến ~N~ trên quầy trưng bày. Chiếc bánh ~i~ thuộc loại ~A_i~. Khách hàng có thể chọn một dãy bánh liên tiếp để mua.

Yêu cầu

Cho biết thông tin của cửa hàng bánh. Hãy xác định số cách mà khách hàng có thể chọn mua, nhưng phải thỏa mãn điều kiện là trong dãy bánh đó số lượng loại bánh đúng bằng ~K~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~K~ ~(N \le 10^5;\ K \le N)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_i~ ~(A_i \le 10^5)~.

Dữ liệu đầu ra

Gồm duy nhất một số nguyên theo yêu cầu.

Ví dụ

Ví dụ 1

INPUT

7 3
2 6 4 3 6 8 3

OUTPUT

7

Giải thích: Có ~7~ cách chọn ~[2, 6, 4]~, ~[6, 4, 3]~, ~[4, 3, 6]~, ~[3, 6, 8]~, ~[6, 8, 3]~, ~[3, 6, 8, 3]~, ~[6, 4, 3, 6]~.

An cũng thích chơi trò chơi trên máy tính, có nhiều trò chơi đòi hỏi thông minh nên không dễ như ăn bánh. Có một trò chơi thu thập năng lượng như sau: Có một dãy ô gồm ~N~ ô vuông, các ô được đánh số từ ~1~ đến ~N~ theo thứ tự từ trái sang phải, ô ~i~ có năng lượng là ~A_i~. Quy tắc để thu thập năng lượng như sau:

• Năng lượng ban đầu là ~0~.
• Lần lượt chọn các ô theo thứ tự từ trái sang phải.
• Nếu lần chọn thứ ~k~ là ô ~j~ thì năng lượng được tăng thêm ~A_i~ (~k~ là số lẻ) hoặc giảm đi ~A_i~ (~k~ là số chẵn).

Người chơi cần xác định cách chọn các ô sao cho tổng năng lượng thu thập được là lớn nhất có thể.

Yêu cầu

Cho biết ~N~ và năng lượng tương ứng trên từng ô là ~A_1, A_2, ..., A_N~. Hãy xác định tổng năng lượng lớn nhất mà An có thể đạt được khi chơi trò chơi được mô tả ở trên.

Dữ liệu đầu vào

Gồm nhiều dòng ứng nhiều bộ dữ liệu cần xác định trong trò chơi, dòng thứ ~i~ chứa thông tin của một bộ dữ liệu thứ ~i~: số đầu tiên là ~N~ (số ~N~ nguyên dương), tiếp theo là ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \le A_i \le 10^4)~ tương ứng là năng lượng trên từng ô.

Dữ liệu đầu ra

Gồm nhiều dòng, dòng thứ ~i~ chứa một số nguyên là tổng năng lượng lớn nhất có thể đạt được theo yêu cầu tương ứng bộ dữ liệu thứ ~i~ trong dữ liệu vào.

Ràng buộc dữ liệu

• Có 75% số test có một bộ dữ liệu vào và ~N \le 10^4~.
• Có 25% số test có hơn một bộ dữ liệu vào và ~1 \le N \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

4 3 1 4 9
3 3 1 4

OUTPUT

11
6