Cho một bảng A kích thước ~m~ x ~n~(~1 \le m,n,\le 100~), trên đó ghi các số nguyên ~a_{ij}~ (~|a_{ij}|\le 100~). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).

Quy tắc đi: Từ ô ~(i,j)~ chỉ được quyền sang một trong 3 ô ~(i;j+1); (i-1;j+1) ; (i+1;j+1)~

Input

• Dòng 1: Ghi hai số m, n tương ứng là số hàng và số cột của bảng.
• m dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng của bảng theo đúng thứ tự từ trái qua phải.

Output

• Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

Ví dụ

Input

5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Output

41

Ràng buộc:

• ~(1 ≤ N,M ≤ 1000; 0 ≤ u_i, k_i ≤ 10^3)~

Ngày 23 tháng 11 năm 2024, Trường đại học Quảng Bình có tổ chức kỳ thi tin học trẻ cho các bạn học sinh trung học phổ thông giao lưu với nhau. Các bạn học sinh THCS cũng háo hức tham gia thử sức dẫu biết là lấy trứng chọi với đá. Có ~N~ học sinh tham gia kỳ thi lập trình được sắp xếp vào 1 dãy máy tính nằm trên một đường thẳng và được đánh số từ 1 đến ~N~ (bạn thứ nhất được đánh số thứ tự là 1). Trong danh sách các bạn tham gia thì số lượng bạn nữ ít hơn khá nhiều so với số lượng bạn nam. Vì thế, ban tổ chức đã không xếp 3 bạn nữ cùng ngồi kế nhau.

Yêu cầu: Hãy cho biết có bao nhiêu cách xếp hàng thỏa mãn điều kiện trên

Input:

• Được cho bởi tệp tht.inp gồm 1 dòng duy nhất chứa số ~N~ (~1 ≤ N ≤ 64~)

Output

• Được cho bởi tệp tht.out gồm 1 dòng chứa số nguyên duy nhất là kết quả tìm được.

Example

Input

3

Output

7

Note

• Với N = 3, giả sử ký hiệu số 0 là bạn nam, số 1 là bạn nữ thì có các cách xếp hàng như sau: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0)

Scoring

• 25% test ứng với 1 ≤ N ≤ 20
• 75% test ứng với 20 < N ≤ 64