Đi ngang qua ô lưới bản khó

Time limit: 1.0s , Memory limit: 256M , Points: 25

REF: OLP Tin học Việt Nam

Cho bảng kích thước $3 \times N$ $3 \times N$ , trong mỗi ô có ghi số $1$ $1$ hoặc $0$ $0$ . Bằng các phép di chuyển $U, D, L, R$ $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$ $S$ . Ban đầu $S$ $S$ nhận giá trị ghi ở ô trên trái, sau mỗi bước giá trị của $S$ $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$ $S$ lớn nhất. Hình bên trên tương ứng với $N = 5$ $N = 5$ và đường đi cần tìm là RDLDRRRRULLURR có giá trị là: $4299$ $4299$

Input

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

Ba dòng tiếp theo chứa 3 xâu các ký tự $0,1$ $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$ $S$ cần tìm.

Samples

Sample Input 1

Copy

Sample Output 1

Copy