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, không làm thay đổi thứ tự còn lại.

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ứ 2
• \(1 \leq\) độ dài mỗi chuỗi \(\leq 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ệ

Scoring

• Thời gian: 1 giây
• Bộ nhớ: 256 MB
• \(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 \(\leq 100\)
• \(75\%\) số test còn lại không có ràng buộc bổ sung

Example

10011010
0101010010

6