Giải bài trực tuyến

LC mới mở ngân hàng. Hầm tiền ngân hàng của LC được thiết kế rất đặc biệt: Đó là 1 hình chữ nhật kích thước 3*n. Tại mỗi ô có ghi 0 hoặc 1. Khi muốn rút tiền ra khỏi ngân hàng, nhân viên phải bắt đầu từ ô trên trái, đi qua hết tất cả các ô của hầm tiền theo các ô kề cạnh với ô đang đứng, mỗi ô đúng 1 lần và đi ra ở 1 ô bất kì phía bên phải. Số tiền rút được ban đầu là 0, mỗi lần đi qua 1 ô, tiền sẽ được nhân đôi và cộng với số ghi ở ô đó. Sau khi hoạt động được 1 thời gian, LC thấy có điều bất cập với ngân hàng của mình: Số tiền mỗi lần rút ra là quá lớn so với lượng cần dùng.

LC muốn biết, với cách rút tiền đặc biệt như vậy thì số tiền lớn nhất có thể rút ra được là bao nhiêu.

Giả thiết rằng LC rất giàu, ngân hàng luôn đủ tiền cho mọi cách rút.

Input

• Dòng đầu tiên ghi số n (n≤300)
• 3 dòng tiếp theo, mỗi dòng ghi 1 xâu nhị phân độ dài n mô tả hầm tiền của ngân hàng.

Output

• Một dòng duy nhất là số tiền lớn nhất có thể rút ra.

Example

Input:
1
1
0
0

Output:
4

Input:
3
010
011
010

Output:
202