REF: OLP Tin học Việt Nam

Cho bảng kích thước ~3 \times N~, trong mỗi ô có ghi số ~1~ hoặc ~0~. Bằng các phép di chuyển ~U, D, L, R~ người ta đi từ ô trên trái của bảng tới ô bất kỳ bên phải nhất của bảng (cột thứ n), không được đi lại vào ô đã đi qua.

Đường đi được đánh giá bằng giá trị ~S~. Ban đầu ~S~ nhận giá trị ghi ở ô trên trái, sau mỗi bước giá trị của ~S~ tăng lên gấp đôi và cộng với nội dung của ô mới đến.

Hãy tìm đường đi tương ứng với ~S~ lớn nhất. Hình bên trên tương ứng với ~N = 5~ và đường đi cần tìm là RDLDRRRRULLURR có giá trị là: ~4299~

Input

Dòng đầu tiên chứa số nguyên ~N~ thỏa ~1 \le n \le 100~.

Ba dòng tiếp theo chứa 3 xâu các ký tự ~0,1~ xác định giá trị ghi trong các ô, liệt kê từ trái sang phải, từ trên xuống dưới.

Output

Giá trị lớn nhất của ~S~ cần tìm.

Samples

Sample Input 1

5
00011
01100
00011

Sample Output 1

4299