Submit solution

Points: 0.94 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.