Giải cứu thành phố

Một thành phố có $n$ toà nhà xếp thành một hàng. Bản đồ mìn của thành phố là một xâu nhị phân độ dài $n$, trong đó ký tự thứ $i$ bằng 1 nếu dưới toà nhà thứ $i$ có mìn, và bằng 0 nếu không có.

Người rà mìn có thể thực hiện hai loại thao tác, mỗi loại lặp lại bao nhiêu lần tuỳ ý và theo thứ tự tuỳ ý:

• Kích nổ một quả mìn đang có dưới toà nhà thứ $x$, tốn $a$ đồng. Khi quả mìn này nổ, nó kích hoạt tiếp hai quả mìn ở hai vị trí $x-1$ và $x+1$ (nếu ở đó có mìn), và phản ứng dây chuyền cứ thế lan ra. Nói cách khác, chỉ cần kích nổ một quả mìn bất kỳ là toàn bộ đoạn mìn liên tiếp chứa nó sẽ nổ hết.
• Đặt thêm một quả mìn xuống một vị trí chưa có mìn, tốn $b$ đồng.

Các vụ nổ không làm hư hại toà nhà nào. Hãy tìm số tiền nhỏ nhất cần chi để cuối cùng trong thành phố không còn quả mìn nào.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa hai số nguyên $a$ và $b$: chi phí kích nổ một quả mìn và chi phí đặt thêm một quả mìn.
  • Dòng thứ hai chứa xâu nhị phân mô tả bản đồ mìn.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số tiền nhỏ nhất cần chi.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le a,b\le 1000$
• Xâu bản đồ chỉ gồm các ký tự 0 và 1, có độ dài ít nhất $1$.
• Tổng độ dài các xâu trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ