GEN và T1 là đôi bạn thân không đội trời chung. Trong trận chung kết của chung kết thế giới năm nay, lẽ ra T1 mạnh hơn GEN rất nhiều và dễ dàng dành chiến thắng. Nhưng vì T1 nhường quá nhiều, khiến kèo đấu trở nên vô cùng căng thẳng và bất phân thắng bại. Vì vậy, ban tổ chức quyết định mời hai đội chơi trò chơi bốc sỏi để tìm ra nhà vô địch.

Ban tổ chức đặt lên bàn \(n\) túi sỏi, các túi được đánh số từ \(1\) đến \(n\). Bên trong túi thứ \(i\) (\(1\le i\le n\)) có \(r_i\) viên sỏi đỏ và \(y_i\) viên sỏi vàng. Ban tổ chức công bố luật bốc sỏi như sau: với túi thứ \(i\), đội chơi có \(4\) lựa chọn bốc sỏi:

• Chỉ lấy \(r_i\) viên sỏi màu đỏ
• Chỉ lấy \(y_i\) viên sỏi màu vàng
• Lấy toàn bộ \(r_i + y_i\) viên sỏi trong túi
• Không lấy viên sỏi nào.

Ban tổ chức đưa ra \(m\) câu đố. Các câu đố được đánh số từ \(1\) tới \(m\). Trong câu đố thứ \(i\), ban tổ chức cho hai số \(t_i\) và \(g_i\) rồi yêu cầu hai đội thử tìm ra một phương pháp lấy sỏi tuân thủ các luật nêu trên, sao cho tổng số viên sỏi đỏ lấy được đúng bằng \(t_i\) và tổng số viên sỏi vàng lấy được đúng bằng \(g_i\).

Trước khi cho các đội suy nghĩ, ban tổ chức công bố cách thức tính điểm. Ban tổ chức có một dãy số \(v_1, v_2, \ldots, v_n\). Ban tổ chức nói rằng, với mọi cặp chỉ số \(a\) và \(b\) thỏa mãn \(1 \leq a \leq b \leq n\), nếu đội chơi tìm ra cách lấy sỏi hợp lệ cho tất cả các câu đố từ \(a\) đến \(b\), đội đó được coi là chinh phục được chuỗi sức mạnh \([a; b]\) và sẽ nhận về số điểm là \(v_a \cdot v_{a + 1} \cdot \ldots \cdot v_{b - 1} \cdot v_b\). Tổng điểm của một đội chơi được tính bằng tổng số điểm nhận về của tất cả các chuỗi sức mạnh mà đội đó chinh phục được.

Lưu ý rằng, các câu đố chỉ là thử tìm một phương án lấy sỏi, chứ không có viên sỏi nào thực sự được lấy ra từ các túi của ban tổ chức. Nói cách khác, \(m\) câu hỏi này là hoàn toàn độc lập, và trong mỗi câu hỏi ta đều có \(n\) túi sỏi với số viên sỏi đỏ và vàng trong túi thứ \(i\) lần lượt là \(r_i\) và \(y_i\).

Là một tê-con chân chính, GSPVHCUTE muốn cổ vũ đtty bằng cách giúp T1 kiếm được nhiều điểm nhất có thể. Các bạn hãy xác định số điểm lớn nhất T1 có thể đạt được nhé.

Input

• Dòng thứ nhất chứa 3 số nguyên \(n\), \(m\) và \(p\) \((1 \le n \le 10^4, 1 \le m \le 3 \cdot 10^5, 1\le p \le 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(r_1, r_2, ..., r_n\) \((1 \le r_i\le 10^4)\).
• Dòng thứ ba chứa \(n\) số nguyên \(y_1, y_2, ..., y_n\) \((1 \le y_i \le 10^4)\).
• Dòng thứ tư chứa \(m\) số nguyên \(t_1, t_2, ..., t_m\) \((0 \le t_i \le 10^5)\).
• Dòng thứ năm chứa \(m\) số nguyên \(g_1, g_2, ..., g_m\) \((0 \le g_i \le 10^5)\).
• Dòng thứ sáu chứa \(m\) số nguyên \(v_1, v_2, ..., v_m\) \((1 \le v_i \le 10^9)\).

Output

Gọi \(S\) là số điểm lớn nhất mà T1 có thể đạt được. In ra một số nguyên không âm duy nhất là phần dư của \(S\) khi chia cho \(p\).

Scoring

• Subtask \(1\) (\(20\) điểm): \(n \le 10\) và \(m \le 200\)
• Subtask \(2\) (\(25\) điểm): \(n \le 10^3\); \(t_i, g_i \le 10^4\) và \(m \le 5000\)
• Subtask \(3\) (\(20\) điểm): \(n \le 10^3\) và \(t_i, g_i \le 10^4\)
• Subtask \(4\) (\(20\) điểm): \(m \le 5000\)
• Subtask \(5\) (\(15\) điểm): Không có ràng buộc gì thêm.

Example

4 7 2271997
2 5 1 8
7 6 3 5
9 6 1 10 16 2 5
9 6 1 10 16 2 5
2 2 7 1 9 9 7

34