Vua Mật Mã

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
ami
Dạng bài
Điểm: 400 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Sau khi đả bại sứa xanh justys, ami hiện đang đối mặt với vua mật mã CaiWinDao. CaiWinDao cho ami tên người yêu cũ thứ 96 của mình, và muốn ami tìm một xâu kí tự có thứ tự từ điển nhỏ nhất và không nhỏ hơn tên người yêu cũ của CaiWinDao. Tuy nhiên, vì căm ghét người yêu cũ, CaiWinDao muốn ami chỉ sử dụng không quá \(cnt_{c}\) kí tự \(c\). Đương nhiên ami đã đưa ra câu trả lời trong 6ms. Các bạn hãy thử sức giải câu đố của vua mật mã CaiWinDao nhé.

Input

  • Dòng đầu tiên chứa 1 số nguyên dương \(n \ (n \leq 10^{3})\) là độ dài tên người yêu cũ của vua mật mã.

  • Dòng tiếp theo một xâu kí tự \(S\) là tên người yêu cũ của CaiWinDao, tên chỉ chứa các kí tự la tinh thường.

  • Dòng tiếp theo chứa 26 số \(cnt_{c_{i}}\), \(c_{i}\) là kí tự la tinh thường thứ \(i\), \(cnt_{c}\) là số kí tự \(c\) tối đa mà ami được phép sử dụng.

Output

  • In ra một xâu kí tự thoả mãn yêu cầu của vua mật mã CaiWinDao. In ra \(-1\) nếu không có xâu kí tự thoả mãn.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(n \leq 20\), \(cnt_{c_{i}} \leq 10^{5}\)

  • Subtask \(2\) (\(20\%\) số điểm): \(n \leq 1000\), \(\Sigma cnt_{c_{i}} \leq 10\)

  • Subtask \(3\) (\(20\%\) số điểm): \(n \leq 1000\), \(cnt_{c_{i}} \leq 10^9\) và vua mật mã chỉ cho phép sử dụng tối đa 2 kí tự.

  • Subtask \(4\) (\(50\%\) số điểm): \(n \leq 10^{3}\), \(cnt_{c_{i}} \leq 10^{9}\)

Example

Test 1

Input 
2
aa
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1
Output 
ab
Note

Ở ví dụ 1, mỗi kí tự chỉ được dùng 1 lần, riêng kí tự \(u\) được dùng 2 lần. Một số xâu thoả mãn là \(amisuper\), \(amibest\) , \(amiop\) , \(cuomngu\) , \(cuomnguthe\) , \(cuomgathiesu\), \(ab\). Xâu \(ab\) có thứ tự từ điển nhỏ nhất và lớn hơn xâu \(aa\).

Test 2

Input 
10
amideptrai
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Output 
az
Note

Ở ví dụ 2, kí tự a được dùng 1 lần, kí tự z được dùng 1 lần. Các xâu thoả mãn là \(a\) , \(az\) , \(z\) , \(za\). Xâu \(az\) có thứ tự từ điển nhỏ nhất và lớn hơn xâu \(amideptrai\). Lưu ý rằng \(a\) có thứ tự từ điểm nhỏ hơn \(amideptrai\) nên không hợp lệ.

Test 3

Input 
10
amideptrai
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output 
-1
Note

Ở ví dụ 3, kí tự a được dùng 1 lần, do đó chỉ có 1 xâu thoả mãn là \(a\). Xâu này có thứ tự từ điển nhỏ hơn \(amideptrai\), do đó không hợp lệ

Bình luận


  • 0
    minhle20168    3:55 p.m. 29 Tháng 7, 2020

    vì sao test ví dụ 2 thì "az" lại có thứ tự từ điển lớn hơn "amideptrai" vậy mn?


    • 0
      tuanlinh    9:13 p.m. 29 Tháng 7, 2020

      so sánh xâu thì k dựa vào độ dài

      4 bình luận nữa