Đánh giá độ mạnh của mật khẩu là một bài toán quan trọng của ngành An Toàn Thông Tin. Trong bài tập này, nhiệm vụ của bạn là đánh giá độ an toàn của một mật khẩu bằng trọng số được gán cho các ký tự:

• Các mật khẩu chỉ bao gồm ký tự tiếng Anh viết thường.
• Mỗi chữ cái tiếng Anh viết thường được gán một trọng số nguyên từ ~0~ đến ~25~ theo cách như sau: Trọng số của ký tự 'a' được cho biết trước. Trọng số các ký tự còn lại được gán theo thứ tự vòng tròn. Ví dụ, nếu trọng số của 'a' là ~5~, trọng số của 'b' sẽ là ~6~, trọng số của 'c' là ~7~, ~\ldots~, trọng số của 'u' là ~25~, trọng số của 'v' là ~0~, ~\ldots~, trọng số của 'z' là ~4~.
• Độ mạnh của một chuỗi mật khẩu là tổng trọng số của các ký tự trong nó.

Yêu cầu: Cho trước một xâu ký tự thể hiện mật khẩu và trọng số của ký tự 'a', hãy tính độ mạnh của mật khẩu đó.

Input

Dòng đầu tiên chứa mật khẩu là một xâu gồm từ ~1~ tới ~100~ chữ cái tiếng Anh in thường. Dòng thứ hai chứa một số nguyên ~x~ duy nhất là trọng số của ký tự 'a' ~(0 \leq x \leq 25)~.

Output

Một số nguyên duy nhất là độ mạnh của mật khẩu đã cho.

Sample Input 1

abc
1

Sample Output 1

6

Sample Input 2

tigersugar
10

Sample Output 2

85

Dãy số ~B = (b_1, b_2, \ldots, b_m)~ được gọi là dãy con của dãy số ~A = (a_1, a_2, \ldots, a_n)~ khi và chỉ khi có thể tạo ra dãy ~B~ bằng cách xóa đi một số phần tử từ dãy ~A~ và giữ nguyên các phần tử còn lại để tạo ra dãy ~B~. Nói cách khác, tồn tại một bộ chỉ số ~i_1, i_2, \ldots, i_m~ sao cho ~1 \leq i_1 < i_2 < \ldots < i_m \leq n~ và ~b_j = a_{i_j}~ với mọi ~1 \leq j \leq m~.

Dãy con tăng dài nhất của một dãy số là dãy con dài nhất thỏa mãn tính chất: mọi phần tử đứng sau đều lớn hơn hẳn các phần tử đứng trước nó.

Cho dãy số ~A = (a_1, a_2, \ldots, a_n)~, bạn được phép đổi dấu (nhân với ~-1~) một dãy con liên tiếp của dãy ~A~. Nói cách khác, bạn được chọn hai chỉ số ~l~ và ~r~ sao cho ~1 \leq l \leq r \leq n~ và biến đổi dãy ban đầu thành ~a_1, a_2, \ldots, a_{l-1}, -a_l, -a_{l+1}, \ldots, -a_{r}, a_{r+1}, a_{r+2}, \ldots, a_n~. Bạn có thể không thực hiện phép biến đổi này nếu không muốn. Hãy biến đổi sao cho độ dài của dãy con tăng dài nhất sau khi biến đổi là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 220797)~. Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(0 \leq |a_i| \leq 10^9)~.

Output

Gồm một số nguyên duy nhất là độ dài lớn nhất của dãy con tăng dài nhất của dãy ~A~ sau khi biến đổi.

Giới hạn

• Subtask ~1~ (~27~ điểm): ~n \leq 10~
• Subtask ~2~ (~41~ điểm): ~n \leq 2207~
• Subtask ~3~ (~32~ điểm): ~n \leq 220797~

Sample Input 1

7
2 2 7 1 9 9 7

Sample Output 1

4

Sample Input 2

9
1 2 3 -4 -5 -6 7 8 9

Sample Output 2

9

Sample Input 3

9
1 2 3 4 5 6 7 8 9

Sample Output 3

9

Sample Input 4

9
9 8 7 6 5 4 3 2 1

Sample Output 4

9

Note

Trong ví dụ thứ nhất, ta biến đổi dãy thành ~(-2, 2, 7, 1, 9, 9, 7)~ để được dãy con tăng dài nhất là ~(-2, 2, 7, 9)~.

Trong hai ví dụ tiếp theo, ta biến đổi dãy thành ~(1, 2, 3, 4, 5, 6, 7, 8, 9)~.

Trong ví dụ thứ tư, ta biến đổi dãy thành ~(-9, -8, -7, -6, -5, -4, -3, -2, -1)~.

Sân vận động Quốc gia Mỹ Đình là nơi diễn ra nhiều trận bóng đá của đội tuyển Việt Nam trong các giải đấu tầm khu vực. Do được xây dựng đã lâu, hệ thống chiếu sáng của sân vận động đã xuống cấp, không đảm bảo tiêu chuẩn về ánh sáng cho các trận đấu được diễn ra vào buổi tối.

Để khắc phục tình trạng này, ban quảy lý sân vận động quyết định xây thêm một số giàn đèn xung quanh sân. Sân vận động được mô phỏng dưới dạng hình chữ nhật, được chia làm ~m~ hàng và ~n~ cột. Một giàn đèn, nếu được lắp đặt sẽ giúp chiếu sáng toàn bộ các ô trên một hàng hoặc một cột của sân. Ban quản lý sẽ lắp đặt một hoặc nhiều giàn đèn khác nhau. Chi phí lắp đặt được xác định như sau: Để lắp giàn đèn chiếu sáng cho hàng ~1, 2, \ldots, m~ mất lần lượt ~r_1, r_2, \ldots, r_m~ đồng. Để lắp giàn đèn chiếu sáng cho cột ~1, 2, \ldots, n~ mất ~c_1, c_2, \ldots, c_n~ đồng.

Khảo sát thực trạng, ban quản lý nhận ra có một số vị trí trên sân hiện đang bị thiếu ánh sáng nghiêm trọng. Ánh sáng tại những ô này bắt buộc phải được cải thiện và hệ thống giàn đèn xây dựng thêm phải chiếu sáng được toàn bộ các ô này. Các bạn hãy giúp ban quản lý lựa chọn vị trí lắp đặt giàn đèn sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên ~\theta~ ~(1 \leq \theta \leq 5)~ là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên ~m~ và ~n~ ~(1 \leq m, n \leq 2207)~ cho biết kích thước hai chiều của sân vận động.
• Dòng thứ ba chứa ~m~ số nguyên ~r_1, r_2, \ldots, r_m~ ~(1 \leq r_i \leq 10^9)~ là chi phí để lắp đặt giàn đèn chiếu sáng cho các hàng.
• Dòng thứ tư chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ ~(1 \leq c_j \leq 10^9)~ là chi phí để lắp đặt giàn đèn chiếu sáng cho các cột.
• ~m~ dòng cuối cùng, mỗi dòng gồm một xâu nhị phân độ dài ~n~. Ký tự thứ ~j~ ở dòng thứ ~i~ là 1 khi và chỉ khi ô ở hàng ~i~ và cột ~j~ phải được chiếu sáng.

Output

• Dòng đầu tiên chứa một số nguyên là tổng chi phí tối thiểu để lắp đặt giàn đèn.
• Dòng thứ hai chứa số nguyên ~x~ cho biết số giàn đèn chiếu sáng hàng được lắp đặt; theo sau là ~x~ số nguyên thể hiện chỉ số của các hàng được lắp giàn đèn.
• Dòng thứ ba chứa số nguyên ~y~ cho biết số giàn đèn chiếu sáng cột được lắp đặt; theo sau là ~y~ số nguyên thể hiện chỉ số của các cột được lắp giàn đèn.

Nếu có nhiều phương án tối ưu, bạn được in ra một đáp án bất kỳ.

Giới hạn

• Subtask ~1~ (~15~ điểm): Tất cả ~m \cdot n~ ô đều phải được chiếu sáng.
• Subtask ~2~ (~15~ điểm): ~m, n \leq 10~
• Subtask ~3~ (~15~ điểm): Số ô phải được chiếu sáng không quá ~20~
• Subtask ~4~ (~15~ điểm): ~m \leq 15~
• Subtask ~5~ (~40~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

2
3 4
2 2 7
1 9 9 7
1011
0100
1011

Sample Output 1

11
3 1 2 3
0

Sample Input 2

2
3 5
7 8 9
1 2 3 4 5
01010
10101
00000

Sample Output 2

14
1 2
2 2 4

Sample Input 3

5
7 21
20000000 2000000 70000 1000 900 90 7
100000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
111111111111111111111
100001110111011011101
101110110111011011101
100001111010111000001
101111111010111011101
101111111101111011101
111111111111111111111

Sample Output 3

22071997
7 1 2 3 4 5 6 7
0

Sample Input 4

2
1 1
1000000000
1000000000
0

Sample Output 4

0
0
0

Một xâu ký tự được gọi là xâu ký tự hằng nếu mọi ký tự của xâu đều giống nhau. Ví dụ, p, vv hay hhh là các xâu ký tự hằng, còn gspvhcute thì không.

Một xâu con liên tiếp của xâu ký tự ~s = s_1 s_2 \ldots s_n~ là xâu ký tự có dạng ~s_l s_{l+1} \ldots s_{r-1} s_r~ với ~1 \leq l \leq r \leq n~. Ví dụ, xâu ppvhhh có ~21~ xâu con liên tiếp, trong đó có ~10~ xâu ký tự hằng: h xuất hiện ~3~ lần, p và hh xuất hiện ~2~ lần, mỗi xâu pp, v và hhh xuất hiện ~1~ lần.

Cho hai số nguyên ~n~ và ~k~, xét tập hợp ~\Omega~ gồm các xâu ký tự ~s~ chỉ gồm chữ cái in thường có chính xác ~n~ xâu con liên tiếp là xâu ký tự hằng. Hãy sắp xếp các xâu ký tự trong ~\Omega~ theo thứ tự từ điển, và in ra xâu ký tự thứ ~k~ trong tập hợp này.

Input

File input gồm ~3~ câu hỏi, mỗi câu hỏi được thể hiện bởi hai số ~n~ và ~k~ được viết trên một dòng với ~1 \leq n \leq 10^7~ và ~1 \leq k \leq 3 \cdot 10^{18}~. Dữ liệu vào đảm bảo số ~k~ không lớn hơn lực lượng của tập hợp ~\Omega~ được định nghĩa ở trên.

Output

Với mỗi câu hỏi, in ra xâu ký tự cần tìm trên một dòng.

Giới hạn

• Subtask ~1~ (~10~ điểm): ~n \leq 2~
• Subtask ~2~ (~14~ điểm): ~n \leq 4~
• Subtask ~3~ (~20~ điểm): ~n \leq 15~ và ~k \leq 10^6~
• Subtask ~4~ (~16~ điểm): ~k = 1~
• Subtask ~5~ (~20~ điểm): ~n \leq 100~
• Subtask ~6~ (~20~ điểm): Không có ràng buộc gì thêm

Sample Input 1

1 1
1 2
1 3

Sample Output 1

a
b
c

Sample Input 2

3 1
3 2
3 3

Sample Output 2

aa
aba
abc

Sample Input 3

2 168
3 9899
4 43749

Sample Output 3

gs
pvh
cute

Sample Input 4

22 7
19 97
56 23

Sample Output 4

aaaaaah
aaaaabaev
aaaaaaaaaax