Nén xâu

Trong quá trình luyện tập cho cuộc thi học sinh giỏi sắp tới, Hùng được thầy giáo giao cho thử sức giải bài toán nén xâu kí tự (chỉ gồm các kí tự la tinh in hoa) sau đây.

Phép cộng trên hai xâu $x$ và $y$, kí hiệu là $x+y$, được hiểu là ghép xâu $y$ liền sau xâu $x$. Xuất phát từ hai xâu $u,v$ và số nguyên $k$, xâu $F_k$ được tạo theo luật sau (còn được gọi là luật tựa Fibonacci):

$$F_1=u;F_2=v;F_3=F_2+F_1;\dots ;F_k=F_{k-1}+F_{k-2}.$$

Ví dụ, với hai xâu $u=$ AB, $v=$ C và $k=5$ ta có: $F_1=$ AB, $F_2=$ C, $F_3=$ CAB, $F_4=$ CABC, $F_5=$ CABCCAB.

Giả sử xâu $T$ có độ dài $n$ là xâu được tạo theo luật trên từ hai xâu xuất phát $u_T,v_T$ có độ dài tương ứng là $n_1,n_2$. Như vậy, $v_T$ là xâu gồm $n_2$ kí tự đầu tiên của xâu $T$ và $u_T$ là xâu gồm $n_1$ kí tự tiếp theo của xâu $T$. Xâu $T$ có thể được nén thành bộ $(u_T,v_T,n)$ vì từ 3 thông tin $u_T,v_T$ và $n$ ta có thể khôi phục được xâu $T$ theo luật trên. Ví dụ xâu $T=$ CABCCAB có thể được nén thành bộ $($AB, C, $7)$.

Một xâu $S$ bất kì có độ dài $m$ cũng có thể được nén theo cách như trên. Với hai số nguyên dương $m_1,m_2$ $(m_1+m_2\le m)$, gọi $v_S$ là xâu gồm $m_2$ kí tự đầu tiên của xâu $S$ và $u_S$ là xâu gồm $m_1$ kí tự tiếp theo trên xâu $S$. Khi đó, xâu $S$ có thể được nén thành bộ $(u_S,v_S,m)$. Tuy nhiên, từ 3 thông tin $u_S,v_S$ và $m$ ta có thể không khôi phục được chính xác xâu $S$. Do đó, người ta đánh giá độ lỗi của phương pháp nén xâu này như sau. Với bộ $(u_S,v_S,m)$, tạo xâu $F_k$ với $k$ nhỏ nhất mà độ dài $F_k$ lớn hơn hoặc bằng $m$ theo luật tựa Fibonacci từ hai xâu xuất phát $F_1=u_S$, $F_2=v_S$. Độ lỗi của việc nén xâu $S$ được tính bằng số lượng vị trí $i$ mà $S[i]$ khác với $F_k[i]$, trong đó $S[i]$ và $F_k[i]$ tương ứng là kí tự thứ $i$ của xâu $S$ và xâu $F_k$ với $i\le m$.

Ví dụ, với $m_1=2$ và $m_2=1$, xâu $S=$ CABACC có độ dài $m=6$ được nén thành bộ $($AB, C, $6)$, sau đó tạo ra xâu $F_5=$ CABCCAB. Khi đó độ lỗi của việc nén xâu $S$ là $2$ do có hai kí tự ở các vị trí thứ 4 và thứ 6 của $S$ và $F_5$ là khác nhau.

Nhận thấy rằng $m_2+m_1$ kí tự đầu tiên của xâu $S$ ảnh hưởng rất lớn đến độ lỗi của việc nén xâu. Vì vậy, người ta tiến hành thay đổi không quá $r$ kí tự trong $m_2+m_1$ kí tự đầu tiên của xâu $S$ để biến xâu $S$ thành xâu $S^{*}$ sao cho độ lỗi của việc nén xâu $S^{*}$ là nhỏ nhất. Việc thay đổi một kí tự là thay kí tự đó bởi một kí tự khác.

Yêu cầu: Cho các số nguyên $m,m_1,m_2,r$ và xâu $S$, hãy tìm cách thay đổi không quá $r$ kí tự trong $m_2+m_1$ kí tự đầu tiên của xâu $S$ để biến xâu $S$ thành xâu $S^{*}$ sao cho độ lỗi của việc nén xâu $S^{*}$ là nhỏ nhất.

Dữ liệu vào

• Dòng thứ nhất chứa bốn số nguyên $m,m_1,m_2,r$ cách nhau bởi dấu cách $(0\le r\le m_2+m_1\le m$; $m_1,m_2\ge 1)$;
• Dòng thứ hai chứa xâu $S$ độ dài $m$, xâu chỉ gồm các kí tự thuộc tập kí tự chữ cái la tinh in hoa (từ A đến Z).

Dữ liệu ra

In ra một số nguyên là độ lỗi nhỏ nhất tìm được.

Ràng buộc

• $m_1,m_2\ge 1$; $0\le r\le m_2+m_1\le m\le {10}^5$.
• $S$ chỉ gồm các chữ cái la tinh in hoa.

Subtasks

• Subtask 1 ($30\%$ số test, $30\%$ số điểm): $r=0$; $m\le {10}^3$;
• Subtask 2 ($40\%$ số test, $40\%$ số điểm): $r=m_1+m_2\le 10$; $m\le {10}^3$ và xâu $S$ chỉ gồm hai kí tự A và B;
• Subtask 3 ($30\%$ số test, $30\%$ số điểm): $m\le {10}^5$.

Ví dụ