Trong đêm trung thu, anh của bé Thu là người phụ trách chuẩn bị các phần quà cho các bạn nhỏ trong xóm. Mỗi phần quà đều có những chiếc bánh trung thu vô cùng hấp dẫn, đa dạng các hương liệu khác nhau từ đậu xanh, đậu đỏ đến khoai môn, trứng muối,... Cụ thể, dự kiến các hộp bánh trung thu sẽ gồm \(n\) loại vị khác nhau, được đánh số từ \(1\) đến \(n\). Máy làm bánh sẽ mất \(a_i\) phút để tạo ra loại bánh thứ \(i\).

Điểm đặc biệt ở chiếc máy là nó sẽ lần lượt hoàn thành các loại bánh theo vòng tròn, tức là với mỗi \(1 \leq i < n\), sau khi sản xuất xong loại bánh thứ \(i\) thì tiếp theo máy chỉ có thể làm ra loại bánh thứ \(i+1\). Khi máy làm xong hộp bánh thứ \(n\) thì nó chỉ có thể tạo ra bánh loại \(1\).

Anh của Thu chỉ có quỹ thời gian \(T\) phút để có thể tạo ra nhiều hộp bánh nhất có thể để tặng cho các bạn nhỏ, nhưng không tính toán được số hộp bánh nhiều nhất là bao nhiêu. Các bạn hãy giúp anh của Thu nhé.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n\) và \(T \ (n \leq 10^5, T \leq 10^{12})\)
• Dòng thứ hai chứa dãy số nguyên dương \(a_1,a_2,...,a_{n} \ (a_i \leq 10^4)\)

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán

Example 1

Input

3 9
2 3 1

Output

4

Giải thích

• Sau \(2\) phút, máy hoàn thành được một hộp bánh loại \(1\).
• Sau \(5\) phút, hoàn thành được một hộp bánh loại \(2\).
• Sau \(6\) phút, hoàn thành được một hộp bánh loại \(3\).
• Sau \(8\) phút, hoàn thành một hộp bánh loại \(1\).
• Sau \(9\) phút, máy không đủ thời gian để hoàn thành thêm một hộp bánh loại \(2\). Tổng cộng, máy làm ra được \(4\) hộp bánh.

Scoring

• Subtask 1 \((50\%)\): \(T \leq \sum{a_i}\)
• Subtask 2 \((50\%)\): Không có ràng buộc gì thêm.

Chị Hằng và chú Cuội đang cảm thấy cô đơn và nhớ trái đất. Họ muốn gửi thông điệp là một số nguyên \(x\) về trái đất, nhưng được mã hóa dưới dạng một xâu \(s\) độ dài \(n\). Giá trị của \(x\) là độ dài lớn nhất của xâu con \(t\) mà khi xóa đi phần xâu \(t\) trong \(s\) thì tồn tại cách sắp xếp các kí tự còn lại để tạo thành một xâu \(s'\) mà tồn tại xâu con của \(s'\) bằng xâu \(t\).

• Một xâu \(t\) được gọi là xâu con của \(s\) nếu ta có thể nhận được \(t\) bằng cách xóa đi một vài kí tự ở đầu (hoặc không xóa kí tự nào) và một vài kí tự ở cuối (hoặc không xóa) của xâu \(s\).

Thu may mắn là người được chọn để nhận thông điệp từ chị Hằng và chú Cuội. Tuy nhiên Thu không biết cách tìm ra giá trị \(x\) được mã hóa, bạn hãy giúp Thu tìm nó nhé.

Input

• Dòng thứ nhất gồm số nguyên dương \(n\) là độ dài xâu \(s \ (n \leq 5*10^6)\)
• Dòng thứ hai chứa xâu \(s\), chỉ gồm các kí tự chữ cái latin thường.

Ouput

• Gồm một dòng duy nhất là giá trị \(x\) tìm được.

Example 1

Input

7
cabcbab

Output

3

Giải thích

• Xâu con \(t=cab\), phần còn lại của \(s\) sau khi bỏ đi \(t\) là \(cbab\), có thể sắp xếp lại thành \(bcab\).

Scoring

• Subtask 1 \((20\%)\): \(n \leq 200\)
• Subtask 2 \((30\%)\): \(n \leq 2000\)
• Subtask 3 \((30\%)\): \(n \leq 10^5\)
• Subtask 4 \((20\%)\): Không có ràng buộc gì thêm.

Khi tham gia một trò chơi trong đêm trung thu, bé Thu gặp bài toán sau:

• Cho \(n\) hộp được xếp thành hình tròn, ban đầu mỗi hộp có \(1\) viên đá. Mỗi lần chơi, bé Thu có thể chọn \(2\) viên đá ở \(2\) hộp khác nhau (\(2\) hộp đó phải còn đá) và di chuyển \(2\) viên đá đó sang \(2\) hộp kề cạnh nhưng ngược chiều nhau.

Bé Thu cần biết mình có thể giành chiến thắng trò chơi bằng cách xác định xem mình có thể chuyển toàn bộ đá về một hộp hay không. Bạn, với tư cách là một lập trình viên không được đi chơi trung thu, hãy giúp bé Thu nhé.

Input

• \(1\) dòng duy nhất là số nguyên dương \(n (n \leq 10^{18}).\)

Output

• In ra \(YES\) nếu bé Thu có thể chiến thắng, ngược lại in ra \(NO\)

Example 1

Input

5

Output

YES

Giải thích

Scoring

• Subtask 1 \((10\%)\): \(n \leq 10\)
• Subtask 2 \((90\%)\): \(n \leq 10^{18}\)

Một tiết mục đáng mong chờ của đêm trung thu ở xóm của Thu, mỗi thiếu nhi sẽ chuẩn bị một phần quà của mình và sẽ trao đổi quà với nhau. Sau đêm trung thu, thiếu nhi thứ \(p_i\) sẽ nhận được quà của thiếu nhi thứ \(i\) và mỗi thiếu nhi nhận được đúng một phần quà. Một một cách chia quà \(p_1, p_2,...,p_n\) được gọi là đẹp nếu có đúng \(k\) thiếu nhi nhận lại quà của chính mình sau đêm trung thu \((p_i = i)\).

Một thao tác được thực hiện bằng cách chọn hai số \(i, j\) thỏa mãn \(1 \leq i, j \leq n, \ i \neq j\) và hoán đổi hai giá trị \((p_i, p_j)\). Tìm số thao tác ít nhất cần thực hiện để cách chia quà được gọi là đẹp.

Input

• Dòng thứ nhất chứa hai số \(n\) và \(k \ (0 \leq k \leq n)\)
• Dòng thứ hai gồm \(n\) số \(p_1, p_2,...,p_{n-1},p_n\).

Output

• Gồm một số duy nhất là đáp án của bài toán. Nếu không tồn cách thực hiện các thao tác, in ra \(-1\).

Example 1

Input

5 2
3 2 5 1 4

Output

1

Giải thích

Thực hiện một thao tác với \((i,j)=(4,5).\) Dãy trở thành \(3, 2, 5, 4, 1\)

Scoring

Gọi \(x\) là số lượng vị trí \(i\) mà \(p_i=i\) trong dãy \(p\) đã cho.

• Subtask 1 \((25\%)\): \(x \geq k, n \leq 1000\)
• Subtask 2 \((25\%)\): \(x \geq k, n \leq 10^5\)
• Subtask 3 \((25\%)\): \(x < k, n \leq 1000\)
• Subtask 4 \((25\%)\): \(x < k, n \leq 3*10^4\)

Khi chơi với xâu, bé Thu bắt gặp bài toán sau

• Cho \(n\) xâu \(s_1, s_2, ..., s_n\) chỉ gồm các ký tự in thường từ \(a \to z.\) Cần tìm \(m\) lớn nhất sao cho tồn tại các chỉ số \(1 \leq i_1 < i_2 < ... < i_m \leq n\) thỏa \(s_{i_1} < s_{i_2} < ... < s_{i_m}.\)

Kí hiệu \(|S|\) là độ dài xâu \(S\)

Xâu \(a\) được gọi là bé hơn \(b\) (kí hiệu \(a < b\)) nếu \(a\) là một tiền tố của \(b\) (\(|a| < |b|,\) với mọi \(i\) thỏa \(1 \leq i \leq |a|\) thì \(a[i] = b[i]\)) hoặc tại vị trí \(i\) đầu tiên mà \(a[i] \neq b[i]\) thì \(a[i] < b[i]\)

Vì tổng độ dài của \(n\) xâu có thể rất lớn nên để tận dụng độ tương đồng của các xâu, các xâu nhập vào sẽ được chia thành \(k\) block khác nhau, mỗi block có dạng như sau:

• Dòng đầu chứa xâu \(S\) là tiền tố của các xâu trong block và \(t\) là số xâu trong block.
• \(t\) dòng tiếp theo, mỗi dòng chứa xâu \(S'.\) Khi đó xâu nhập vào là \(S + S'.\) Xem giải thích để hiểu rõ hơn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n (n \leq 10^5)\) là số xâu và \(k(k \leq n)\) là số block.
• \(k\) block tiếp theo, dòng đầu mỗi block chứa xâu \(S\) và số nguyên dương \(t.\) \(t\) dòng tiếp theo trong mỗi block, mỗi dòng chứa xâu \(S'\)

Dữ liệu đảm bảo tổng dộ dài các xâu \(S\) và \(S'\) không vượt quá \(10^6\) và tổng các \(t\) bằng \(n.\)

Output

• In ra \(m\) là số lượng xâu lớn nhất

Example 1

Input

7 3
aa 2
bb
cc
abc 3
bca
acc
bbb
bb 2
ac
aa

Output

5

Giải thích

\(s_1 = aabb\)
\(s_2 = aacc\)
\(s_3 = abcbca\)
\(s_4 = abcacc\)
\(s_5 = abcbbb\)
\(s_6 = bbac\)
\(s_7 = bbaa\)

Chọn các xâu \(s_1 <s_2 < s_3 < s_5 < s_6\)

Scoring

• Subtask 1 \((50\%)\): \(n \leq 300, |s_1| + |s_2| + ... + |s_n| \leq 2000.\)
• Subtask 2 \((50\%)\): Không có ràng buộc gì thêm.