Tạo xâu

Bạn cần tạo ra một xâu $t$. Để làm điều đó, bạn có $n$ xâu $s_1,s_2,\dots ,s_n$ và phải thực hiện đúng $|t|$ thao tác ($|t|$ là độ dài của $t$). Mỗi thao tác gồm:

1. Chọn một xâu không rỗng bất kỳ trong các xâu $s_1,s_2,\dots ,s_n$.
2. Chọn một ký tự bất kỳ trong xâu đó và ghi ký tự này ra giấy.
3. Xóa ký tự vừa chọn khỏi xâu đó.

Sau mỗi thao tác, tổng số ký tự trong các xâu giảm đi $1$. Bạn tạo được xâu $t$ nếu các ký tự đã ghi ra giấy, theo đúng thứ tự thực hiện thao tác, ghép lại thành đúng xâu $t$.

Ngoài ra còn có các ràng buộc sau. Với mỗi xâu $s_i$ bạn biết một số $a_i$ là số ký tự tối đa được phép xóa khỏi $s_i$. Đồng thời, mỗi thao tác xóa một ký tự khỏi xâu $s_i$ tốn $i$ đồng. Nghĩa là thao tác trên $s_1$ rẻ nhất (tốn $1$ đồng), còn thao tác trên $s_n$ đắt nhất (tốn $n$ đồng).

Hãy tính số tiền nhỏ nhất (tính bằng đồng) cần bỏ ra để tạo xâu $t$. Chi phí tạo xâu $t$ là tổng chi phí của các thao tác đã dùng. Nếu không có cách nào tạo được $t$, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa xâu $t$.
• Dòng thứ hai chứa một số nguyên $n$ là số xâu được phép thao tác.
• Mỗi dòng trong $n$ dòng tiếp theo chứa một xâu $s_i$ và một số nguyên $a_i$, cách nhau bởi dấu cách. $a_i$ là số ký tự tối đa được phép xóa khỏi $s_i$.

Tất cả các xâu chỉ gồm các chữ cái Latinh in thường và đều không rỗng.

Dữ liệu ra

In ra một số duy nhất là số tiền nhỏ nhất cần bỏ ra để tạo xâu $t$. Nếu không có lời giải, in ra $-1$.

Ràng buộc

• $1\le n\le 100$
• $0\le a_i\le 100$
• Độ dài của $t$ và của mỗi $s_i$ không vượt quá $100$.

Ví dụ