Du lịch vui vẻ

Khải rất yêu du lịch. Một ngày Khải được mẹ cho rất nhiều tiền để bay sang Nhật Bản tham gia các sự kiện về văn hóa Nhật, Khải vô cùng thích thú. Khải đã tìm hiểu kĩ thông tin các sự kiện diễn ra, và cậu nhận thấy rằng nếu cậu tham gia được sự kiện \(i\) thì sẽ tăng lên độ vui vẻ là \(v_i\). Dịp này ở nhật bản có rất nhiều sự kiện được tổ chức, cụ thể có \(N\) sự kiện \(s_1,s_2,…,s_N\) (\(s_i\in [1,K]\)) diễn ra theo thứ tự (có nhiều sự kiện có thể lặp lại). Cá nhân Khải thì lại muốn tham gia các sự kiện theo thứ tự \(t_1,t_2,…,t_M\) (\(t_i\in [1,K]\)), tất nhiên nếu cậu tham gia được sự kiện \(t_i\) thì độ vui vẻ của cậu sẽ được cộng thêm \(v_(t_i)\). Tuy nhiên, việc Khải muốn tham gia các sự kiện theo thứ tự ưa thích dẫn tới việc sẽ có một số sự kiện của Nhật Bản mà Khải không tham gia được hay là các sự kiện mà Khải muốn tham gia cũng không tham gia được. Khải tính ra rằng nếu cậu bỏ qua các sự kiện ưa thích \(t_p,t_(p+1),…,t_q\) (\(q\geq p\), \(q-p+1\) sự kiện ưa thích liên tiếp) thì độ vui vẻ của cậu giảm xuống một lượng \(-(A+(q-p+1).B)\). Một điều nữa, nếu như Khải tham gia hai sự kiện \(s_p\) và \(s_q\) (\(p+2\leq q\)) mà không tham gia sự kiện nào giữa hai sự kiện này thì độ vui vẻ của cậu cũng giảm xuống một lượng \(-(A+(q-p-1)B)\).

Yêu cầu: Tìm độ vui vẻ lớn nhất mà Khải có thể có được.

Input

• Dòng đầu gồm các số nguyên dương \(K,N,M,A\) và \(B\) theo thứ tự (\(K\leq 1000;n,m\leq 5000;-100\leq A,B\leq 0\)).

• Dòng thứ hai chứa \(K\) số nguyên dương \(v_1,v_2,…,v_k\) (\(1\leq v_i\leq 100\)).

• Dòng thứ ba chứa \(N\) số nguyên dương \(s_1,s_2,…,s_N\) (\(s_i\in [0,K]\)).

• Dòng thứ 4 chứa \(M\) số nguyên dương \(t_1,t_2,…,t_M\) (\(t_i\in [0,K]\)).

Output

• In ra kết quả bài toán là độ vui vẻ lớn nhất của Khải.

Example

1 5 3 -5 -4
10
1 1 1 1 1
1 1 1

30

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(K=1; M\leq N \leq 10^3\).

• Subtask \(2\) (\(15\%\) số điểm): \(K=1; N<M\leq 10^3\).

• Subtask \(3\) (\(15\%\) số điểm): \(A=B=0\).

• Subtask \(4\) (\(15\%\) số điểm): \(A=0\).

• Subtask \(5\) (\(15\%\) số điểm): \(B=0\).

• Subtask \(6\) (\(15\%\) số điểm): \(N,M<100\).

• Subtask \(7\) (\(15\%\) số điểm): Không có giới hạn gì thêm.