# Kén rể
Con gái phú ông đã đến tuổi trưởng thành, vì vậy phú ông quyết định mở cuộc thi kén rể để tìm ra người đàn ông xứng đáng có thể chăm lo cho cuộc đời của con gái ông và cơ nghiệp của ông sau này. Ông ra một câu đố như sau:

Cho một xâu $s$ độ dài $n$ chỉ gồm $26$ kí tự in thường, trong đó có $k$ xâu con được phú ông coi là xấu. Phú ông có một xâu $t$ độ dài $m$, ông muốn thay đổi một số kí tự của xâu $t$ sao cho không có bất kì xâu nào trong số $k$ xâu con xấu của xâu $s$ xuất hiện trong $t$. Mỗi một lượt, người đang tham gia cuộc thi sẽ được phép chọn một vị trí bất kì của xâu $t$ và thay đổi nó bằng một kí tự khác.

Người thực hiện ít lượt đi nhất sẽ chiến thắng cuộc thi và được làm rể nhà phú ông. Tèo và con gái phú ông đã có tình ý với nhau từ lâu, vì không thể cãi lời cha, nên chỉ có cách Tèo chiến thắng cuộc thi thì hai người mới có thể đến với nhau. Hãy giúp tèo tính số lượt ít nhất cậu cần dùng. Nếu Tèo không có cách nào để vượt qua thử thách, in ra -1.

Input:
Dòng đầu tiên chứa xâu $s$ độ dài $n$ $(n \leq 100)$.

Dòng thứ hai chứa xâu $t$ độ dài $m$ $(m \leq 100)$.

Dòng thứ ba chứa số nguyên $k$ là số xâu con xấu $(0 \leq k \leq \frac{n * (n+1)}{2})$.

$k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i, r_i$ mô tả xâu con xấu thứ $i$. $(1 \leq l_i \leq r_i \leq n)$. Dữ liệu đảm bảo mọi cặp $l_i, r_i$ là phân biệt.

Output:

Một số nguyên duy nhất là số lượt ít nhất Tèo cần dùng.

Scoring:

Subtask $1$: $s_{l_i} = s_{l_i+1} =... = s_{r_i}$ với mọi $1 \leq i \leq k$.

Subtask $2$: $k=1$ và $l_1 = 1, r_1 = n$.