Tại Tây Ninh nơi nổi tiếng với mật ong hoa rừng quý hiếm, Huy đang mô phỏng trên mặt phẳng hai chiều hành trình một chú ong chăm chỉ đang thu hoạch mật ngọt trên một tổ ong tự nhiên hình lục giác.

Tổ ong được cấu tạo từ các ô lục giác đều sắp xếp thành một lưới tổ ong có dạng đặc biệt gọi là hệ tọa độ lục giác, trong đó mỗi ô được định danh bởi bộ tọa độ ~(q,r,s)~ thỏa mãn ~q+r+s=0~ như hình vẽ dưới đây.

Một lưới lục giác kích thước ~M~ là tập hợp tất cả các ô tọa độ ~(q,r,s)~ thỏa mãn ~\max(|q|,|r|,|s|) \le M~. Như vậy số lượng ô của lưới lục giác là ~1+3 \times M \times (M+1)~. Mỗi ô ~(q,r,s)~ chứa một giá trị ~A_{q,r,s}~ thể hiện lượng mật ngọt mà chú ong có thể thu thập tại đó.

Một chú ong đang tìm mật trên một tổ ong có dạng lưới lục giác kích thước ~M~. Ở ô ~(q,r,s)~, chú ong có thể di chuyển theo các hướng sau:

• Hướng phải (R): ~(q,r,s) \rightarrow (q+1,r,s-1)~ ~(-M \le q < M,\ -M \le r \le M,\ -M < s \le M)~.

• Hướng xuống trái (DL): ~(q,r,s) \rightarrow (q-1,r+1,s)~ ~(-M < q \le M,\ -M \le r < M,\ -M \le s \le M)~.

• Hướng xuống phải (DR): ~(q,r,s) \rightarrow (q,r+1,s-1)~ ~(-M \le q \le M,\ -M \le r < M,\ -M < s \le M)~.

Ban đầu, chú ong đứng ở vị trí ~(0,-M,+M)~ là đỉnh trên của lưới, chú muốn đi qua các ô để lấy mật ngọt và kết thúc hành trình ở một ô định trước.

Yêu cầu: Hãy tìm tổng lượng mật lớn nhất mà chú ong có thể thu được nếu di chuyển từ ô xuất phát đến ô kết thúc.

Input

• Dòng đầu tiên chứa số nguyên dương ~M~ thể hiện kích thước của tổ ong ~(1 \le M \le 100)~.

• Dòng thứ ~i~ trong số ~1+3 \times M \times (M+1)~ dòng tiếp theo chứa bốn số nguyên ~q_i,r_i,s_i,A_{q_i,r_i,s_i}~ ~(1 \le A_{q_i,r_i,s_i} \le 10^6)~ lần lượt thể hiện tọa độ của một ô thuộc lưới lục giác và giá trị tương ứng của ô đó. Dữ liệu đảm bảo tất cả các ô của lưới đều được liệt kê.

• Dòng cuối cùng chứa ba số nguyên ~X,Y,Z~ thể hiện tọa độ của ô cần đến thuộc lưới đã cho.

Output

Một số nguyên duy nhất thể hiện tổng số lượng mật thu được trong phương án tối ưu.

Scoring

Sample Input 1

1
0 0 0 5
0 -1 1 5
0 1 -1 5
-1 0 1 5
1 0 -1 5
-1 1 0 5
1 -1 0 5
0 1 -1

Sample Output 1

25

Notes

Một đường đi tối ưu của chú ong sẽ lần lượt đi qua các ô sau:

~(0,-1,+1), (+1,-1,0), (0,0,0), (+1,0,-1), (0,+1,-1)~

với tổng số lượng mật thu được là ~5+5+5+5+5=25~.