Cho ~2~ xâu ký tự ~S~ và ~T~ trong đó ~S~ chỉ bao gồm các ký tự 'a' ~\rightarrow~ 'z' còn ~T~ chỉ bao gồm các ký tự 'a' ~\rightarrow~ 'z' và ~2~ ký tự đặc biệt là '?' và '*'.
Một ký tự '*' trong xâu ~T~ có thể đại diện cho ~1~ số lượng bất kỳ (có thể bằng ~0)~ các ký tự 'a' ~\rightarrow~ 'z'.
Một ký tự '?' trong xâu ~T~ có thể đại diện cho đúng 1 ký tự trong số các ký tự 'a' ~\rightarrow~ 'z'.
Một xâu ~X~ gọi là thỏa mãn định dạng ~T~ nếu ta có thể thay các ký tự '*' và '?' trong xâu ~T~ để thu được xâu ~X~.
Ví dụ
~T =~'*bc?' sẽ có các xâu ~X~ thỏa mãn như 'abca', 'bca', 'bcd', 'aaaaabcz', ... Trọng số của một xâu được tính bằng tổng trọng số của các ký tự có trong đó với quy ước 'a' ~= 1~, 'b' ~= 2~, 'c' ~= 3~, ...'z' ~= 26~.
Yêu cầu:
Hãy tìm xâu ~X~ là xâu con liên tiếp của xâu ~S~ mà ~X~ thỏa mãn định dạng ~T~ và có trọng số là nhỏ nhất.
Input
Gồm ~1~ dòng chứa ~2~ xâu ~T~ và ~S~ ~(1 \leq |S| \leq 10000, |T| \leq 1000)~
Output
Ghi ra trọng số của xâu ~X~ tìm được, hoặc ghi ra ~- 1~ nếu không có xâu ~X~ nào thỏa mãn.
Sample Input 1
a?a alabala
Sample Output 1
4
Sample Input 2
a*c?a axcbaabcbax
Sample Output 2
9
Note
Ở test ví dụ 1: aba
là xâu có trọng số nhỏ nhất tìm được.
Ở test ví dụ 2: abcba
có trọng số nhỏ hơn axcba
Bình luận