Bài tập

Ta nén một xâu chữ cái thường theo quy tắc sau. Một biểu diễn nén \(S\) là dãy gồm một hoặc nhiều phần tử \(R\) viết liền nhau, mỗi \(R\) là:

• một chữ cái thường a..z; hoặc
• có dạng D(S), trong đó \(D \ge 2\) là số nguyên viết bằng chữ số thập phân (không có số \(0\) đứng đầu) và \(S\) là một biểu diễn nén; nó biểu thị \(S\) (sau khi giải nén) được lặp lại \(D\) lần liền nhau.

Ví dụ abababaaaaa có thể viết là 3(ab)5(a).

Cho xâu \(A\) gồm \(N\) chữ cái thường. Hãy tìm biểu diễn nén của \(A\) có độ dài ngắn nhất (tính cả chữ số và dấu ngoặc). Nếu có nhiều biểu diễn cùng độ dài ngắn nhất, chọn biểu diễn nhỏ nhất theo thứ tự từ điển tính theo mã ASCII (( = 40, ) = 41, chữ số = 48..57, chữ cái thường = 97..122).

Input

• Dòng đầu là số nguyên \(N\).
• Dòng thứ hai là xâu \(A\) gồm \(N\) chữ cái thường.

Output

• In ra biểu diễn nén tìm được trên một dòng.

Constraints

• \(1 \le N \le 300\)
• Ở \(60\%\) số test \(N \le 10\); ở \(20\%\) số test \(N \le 25\) và xâu chỉ gồm a, b.

Sample Input

12
aabaabaabxyy

Sample Output

3(aab)xyy

Explanation

aab lặp \(3\) lần rồi đến xyy; biểu diễn 3(aab)xyy có độ dài \(9\), ngắn hơn xâu gốc.

Ban tổ chức một kỳ thi chia thí sinh dự kiến thành ba nhóm: có \(a\) thí sinh ở nhóm 1 (mỗi người được đánh giá \(500\) điểm), \(b\) thí sinh ở nhóm 2 (mỗi người \(1000\) điểm) và \(c\) thí sinh ở nhóm 3 (mỗi người \(1500\) điểm). Mức độ thành công của kỳ thi là tổng điểm đánh giá của tất cả thí sinh.

Hãy tính mức độ thành công đó.

Input

Một dòng chứa ba số nguyên dương \(a, b, c\).

Output

In ra mức độ thành công: \(500a + 1000b + 1500c\).

Constraints

• \(1 \le a, b, c \le 100\)

Sample Input

3 2 1

Sample Output

5000

Explanation

\(3 \cdot 500 + 2 \cdot 1000 + 1 \cdot 1500 = 5000\).

Một máy ATM đang chứa \(n\) tờ tiền, tờ thứ \(i\) có mệnh giá \(T_i\) (các tờ được đánh số từ \(1\) đến \(n\), hai tờ khác nhau có thể cùng mệnh giá). Khách hàng muốn rút đúng \(M\) đồng. Máy chỉ được phát một số tờ tiền có sẵn (mỗi tờ dùng tối đa một lần) sao cho tổng mệnh giá các tờ phát ra đúng bằng \(M\).

Hãy cho biết máy sẽ phát những tờ nào. Nếu không thể phát đủ đúng \(M\) đồng thì máy in ra thông báo khongtherut.

Để đáp án là duy nhất, hãy chọn cách phát mà dãy chỉ số các tờ tiền được phát (sắp tăng dần) nhỏ nhất theo thứ tự từ điển.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(M\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(T_1, T_2, \dots, T_n\).

Output

• Nếu không có cách phát nào, in ra khongtherut.
• Ngược lại, dòng đầu in số lượng tờ tiền được phát, dòng thứ hai in chỉ số của các tờ đó theo thứ tự tăng dần, cách nhau một dấu cách.

Constraints

• \(1 \le n \le 22\)
• \(1 \le M \le 10^{12}\)
• \(1 \le T_i \le 10^9\)

Sample Input

6 9000
2000 5000 1000 3000 4000 1000

Sample Output

4
1 2 3 6

Explanation

Các tờ số \(1, 2, 3, 6\) có mệnh giá \(2000 + 5000 + 1000 + 1000 = 9000\). Không có tập chỉ số nào nhỏ hơn theo thứ tự từ điển cho đúng \(9000\) đồng.

Một trang trại có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Chủ trang trại vừa mua một chiếc máy vắt sữa rất kén chọn: mỗi ngày người ta chọn ra một nhóm bò (có thể là bất kỳ tập con nào của đàn, các con bò được phân biệt với nhau kể cả khi cho cùng lượng sữa) và máy chỉ chạy đúng khi tổng lượng sữa của nhóm đúng bằng \(M\).

Hãy cho biết:

1. Có bao nhiêu nhóm bò khác nhau có tổng lượng sữa đúng bằng \(M\).
2. Trong các nhóm như vậy, nhóm nhỏ nhất có bao nhiêu con bò.

Dữ liệu luôn đảm bảo có ít nhất một nhóm thỏa mãn.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(M\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

In ra hai số nguyên cách nhau một dấu cách: số nhóm bò có tổng đúng \(M\) và số con bò ít nhất trong một nhóm như vậy.

Constraints

• \(1 \le n \le 20\)
• \(1 \le M \le 2 \cdot 10^9\)
• \(1 \le a_i \le 10^8\)

Sample Input

6 9
4 5 2 7 3 2

Sample Output

6 2

Explanation

Sáu nhóm có tổng bằng \(9\) là: \(4+5\); \(7+2\) (có hai cách chọn vì có hai con cho \(2\) đơn vị); \(4+3+2\) (hai cách); \(5+2+2\). Nhóm nhỏ nhất gồm \(2\) con.