Một hệ thống giám sát an toàn ghi lại trạng thái cảnh báo của hai cảm biến độc lập trong cùng một khoảng thời gian. Mỗi cảm biến lưu dữ liệu dưới dạng chuỗi nhị phân:

• 0: trạng thái an toàn;
• 1: trạng thái cảnh báo.

Do độ nhạy khác nhau, hai cảm biến có thể ghi nhận khác nhau ở một số thời điểm. Để đánh giá độ tin cậy, kỹ sư cần xác định một kịch bản cảnh báo chung dài nhất xuất hiện trong cả hai bản ghi, sao cho kịch bản đó có cấu trúc:

1. Giai đoạn an toàn (chỉ gồm 0)
2. Giai đoạn cảnh báo liên tục (chỉ gồm 1)
3. Giai đoạn trở lại an toàn (chỉ gồm 0)

Mỗi giai đoạn có thể rỗng, nhưng thứ tự ba giai đoạn phải được giữ nguyên. Kịch bản chung có thể được trích xuất bằng cách loại bỏ một số thời điểm đo trong mỗi bản ghi, nhưng làm thay đổi thứ tự còn lại. Tính độ dài lớn nhất của một kịch bản cảnh báo chung thỏa mãn điều kiện trên.

Yêu cầu: Tìm độ dài lớn nhất của kịch bản chung hợp lệ.

Input

Gồm 2 dòng: dòng 1 chứa chuỗi nhị phân của cảm biến thứ nhất, dòng 2 chứa chuỗi nhị phân của cảm biến thứ hai; (~1 \le~ độ dài mỗi chuỗi ~\le 5000~).

Output

In ra một số nguyên là độ dài lớn nhất của kịch bản chung hợp lệ.

Sample Input 1

10011010
0101010010

Sample Output 1

6

Giới hạn

• 10% số test có ràng buộc bổ sung: Cả hai xâu chỉ gồm ký tự '0' hoặc chỉ gồm ký tự '1'.
• 15% số test khác có ràng buộc bổ sung: độ dài của mỗi chuỗi ~\le 100~.
• 75% số test còn lại không có ràng buộc bổ sung.