Angels

Đề bài được lấy cảm hứng từ bộ anime Evangelion.

Vào năm 2037, Trái Đất đã trải qua Chấn động Thứ hai (Chấn động Thứ nhất là vụ va chạm thiên thạch thời tiền sử đã xóa sổ loài khủng long). Vào thời điểm này, nước biển dường như chuyển sang màu đỏ và những thực thể khổng lồ, kỳ quái xuất hiện; các nhà khoa học gọi chúng là các Angel. Có nhiều manh mối cho thấy những Angel này là các thực thể cổ xưa nằm sâu trong lòng đất, dưới lớp băng dày ở Nam Cực. Chấn động Thứ hai đã đánh thức chúng. Các Angel không có bất kỳ quy chuẩn chung nào về hình dạng: chúng có thể mang hình dáng của một con nhện, một con mực, một trạm vũ trụ, hay thậm chí là hình dạng con người. Angel giống như những sinh vật đại diện cho sự sống trên Trái Đất, ngoại trừ việc chúng to lớn hơn gấp bội — to lớn một cách phi lý — và luôn sẵn sàng hủy diệt mọi thứ. Chúng không cần ăn uống, và thậm chí không có bất kỳ dữ liệu nào về cách thức chúng xuất hiện hay biến mất. Mục tiêu duy nhất của một Angel là hợp nhất với Lilith (Angel thứ hai, đang bị phong ấn bởi Ngọn giáo Longinus bên trong NERV). Các nhà khoa học tin rằng tuyệt đối không được để Lilith tiếp xúc với các Angel khác, bởi điều đó sẽ kích hoạt Chấn động Thứ ba do xung đột trong cấu trúc gen giữa các Angel.

Cấu trúc gen của một Angel có thể được biểu diễn bằng một dãy số có tối đa 5000 phần tử. Các nhà khoa học tại căn cứ quân sự NERV đã thiết lập một phương trình đo lường mức độ tương tác giữa 2 Angel; họ gọi đó là Anti-Angel. Phương trình được định nghĩa như sau:

Gọi dãy A gồm N phần tử là dãy số biểu diễn mã gen của Angel 1, và dãy B gồm M phần tử là mã gen của Angel 2.

Gọi C gồm K phần tử là một dãy con chung bất kỳ (không nhất thiết phải liên tiếp nhưng phải giữ nguyên thứ tự xuất hiện) của A và B. $F_{C} = \sum_{i = 2}^{K} (C_i + (-1)^i \times C_{i-1}) ^ 2$

$F_{AB} = \max F_{C}$ (nói cách khác là giá trị F_C lớn nhất trong tất cả các dãy con chung C có thể chọn) chính là giá trị Anti-Angel giữa Angel A và Angel B.

Lưu ý: Nếu độ dài của $C < 2$, giá trị F_C hiển nhiên bằng 0.

Nhờ phương trình này, các nhà khoa học có thể giải thích lý do tại sao sự tương tác giữa Lilith và các Angel khác lại gây ra Chấn động Thứ ba. Tuy nhiên, mã gen có vô số tổ hợp khả dĩ và mã gen của Angel không giống như con người — chúng là các số nguyên. Họ cần phương pháp tính toán giá trị phương trình trên một cách nhanh nhất có thể để kịp thời công bố nghiên cứu của mình.

Với vai trò là Trưởng Hệ thống Thuật toán tại NERV, bạn hãy giúp các nhà khoa học giải quyết bài toán trên.

Đầu vào:

• Dòng đầu tiên chứa 2 số nguyên N và M.
• Dòng tiếp theo chứa N số nguyên cách nhau bởi dấu cách $A_1, A_2, ..., A_N$.
• Dòng tiếp theo chứa M số nguyên cách nhau bởi dấu cách $B_1, B_2, ..., B_M$.

Giới hạn

• $1 \leq N, M \leq 5000$
• $-10^5 \leq A_i, B_i \leq 10^5$

Đầu ra:

• In ra một số nguyên duy nhất là kết quả của $F_{AB}$.

Subtask (tham khảo)

• $20\%$ số test có $1 \leq N, M \leq 500$ và $0 \leq A_i, B_i \leq 100$.
• $80\%$ số test còn lại tuân theo giới hạn gốc của đề bài.

Giải thích: Dãy con chung C mang lại giá trị $F_{C}$ lớn nhất là $C = \{5, 2, 3, 7\}$.

$F_{AB} = (5+2)^2 + (2-3)^2 + (3+7)^2 = 150$.

Ví dụ 1:

Đầu vào:

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

Đầu ra:

150