Có \(N\) bóng đèn xếp thành một hàng trong một hành lang dài, được đánh số từ \(1\) đến \(N\). Mỗi bóng đèn ở một trong hai trạng thái: tắt hoặc bật. Một cơ chế đặc biệt cho phép thay đổi trạng thái của các bóng đèn. Trong một thao tác, bạn có thể thực hiện một trong các việc sau:

• Chọn hai số nguyên \(p,q\) thỏa mãn \(1 \le p \le q \le N\) và tắt tất cả các bóng đèn \(p,p+1,\ldots,q\).
• Chọn hai số nguyên \(p,q\) thỏa mãn \(1 \le p \le q \le N\) và bật tất cả các bóng đèn \(p,p+1,\ldots,q\).
• Chọn hai số nguyên \(p,q\) thỏa mãn \(1 \le p \le q \le N\) và đảo trạng thái của tất cả các bóng đèn \(p,p+1,\ldots,q\): bóng đang tắt chuyển thành bật, bóng đang bật chuyển thành tắt.

Trạng thái hiện tại được biểu diễn bằng xâu \(A\) có độ dài \(N\). Ký tự thứ \(i\) của \(A\) là 0 nếu bóng đèn \(i\) đang tắt, và là 1 nếu bóng đèn đó đang bật. Bạn muốn đưa các bóng đèn về trạng thái được biểu diễn bằng xâu \(B\) có độ dài \(N\), sử dụng ít thao tác nhất có thể. Ký tự thứ \(i\) của \(B\) là 0 nếu bóng đèn \(i\) cần tắt, và là 1 nếu bóng đèn đó cần bật.

Hãy tính số thao tác ít nhất cần thực hiện để đạt được trạng thái mong muốn.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
A
B

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số thao tác ít nhất cần thực hiện.

Ràng buộc

• \(1 \le N \le 1\,000\,000\).
• \(A\) và \(B\) là hai xâu có độ dài \(N\).
• Mỗi ký tự của \(A\) và \(B\) là 0 hoặc 1.

Phân nhóm

1. \(6\) điểm: \(N \le 18\).
2. \(41\) điểm: \(N \le 2\,000\).
3. \(4\) điểm: Mọi ký tự của \(A\) đều là 0.
4. \(49\) điểm: Không có ràng buộc bổ sung.

Ví dụ

8
11011100
01101001

4

13
1010010010100
0000111001011

3

18
001100010010000110
110110001000100101

5

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 3 (22/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.