Програмчлалын олимпиадын бодлогын архив

2*N ширхэг гэрлийг 2 мөр, N багана үүсгэхээр өрж тавьжээ. Гэрэл бүр ассан, унтарсан төлөвт байж болох ба анх бүх гэрэл унтарсан төлөвт байна.

Бид зарим гэрлүүдийг асааж тодорхой дүрс үүсгэх ёстой. Нэг алхамд бид нэг мөр эсвэл багананд байгаа дараалсан гэрлүүдийн (нэг эсвэл хэд хэдэн гэрлүүдийн) төлвийг сольж чадна.

Үүсгэх ёстой дүрс өгөгдсөн бол уг дүрсийг гаргаж авахын тулд хамгийн багадаа хэдэн алхам хэрэгтэйг ол. Доорх хүснэгтэнд Жишээ 3-т өгөгдсөн дүрсийг гаргаж авах 7-н алхамыг үзүүлэв:

Input

Эхний мөрөнд баганын тоог илэрхийлэх N бүхэл тоо өгөгдөнө (1<=N<=10000).

Дараагийн хоёр мөрөнд гаргаж авах ёстой дүрсийг илэрхийлэх тоонууд байрлана.

1 гэсэн тэмдэгт нь эцсийн байрлалд уг гэрэл ассан төлөвт байх ёстойг, 0 гэсэн тэмдэгт унтарсан төлөвт байх ёстойг илэрхийлнэ.

Output

Өгөгдсөн дүрсийг гаргаж авахад шаардагдах алхмуудын тооны хамгийн бага утга.

Example

Input:
3
100
000

Output:
1

Input:
5
11011
11011

Output:
3


Input:
20
11101101111000101010
01111101100000010100

Output:
7