Nhà hàng HakyFood mới mở có ~n~ món chính và ~m~ món điểm tâm. Giá của các món chính biểu diễn bởi mảng ~a~, giá của các món điểm tâm biểu diễn bởi mảng ~b~.

Để thu hút nhiều khách hàng hơn, HakyFood quyết định ra mắt combo mới. Một combo tùy chọn sẽ gồm một món chính và một món điểm tâm. Nếu gọi ~x~ là tổng giá tiền hai món, thì giá tiền của combo sẽ là ~min(x, p)~ với ~p~ là số may mắn của Per.

Có rất nhiều cách tạo combo như vậy nên HakyFood muốn thử tính xem tổng tiền các combo đó là bao nhiêu. Các bạn hãy giúp HakyFood nhé!

Input

Dòng đầu chứa số nguyên ~n~, ~m~, ~p~ (~1 \le n, m \le 2.10^5~, ~1 \le p \le 2.10^8~)  – Số lượng món chính và món điểm tâm và số may mắn của HakyFood.

Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ (~1 \le a_i \le 2.10^8~)  – Mô tả giá tiền các món chính.

Dòng tiếp theo chứa ~m~ số nguyên ~b_j~ (~1 \le b_j \le 2.10^8~)  – Mô tả giá tiền các món điểm tâm.

Output

In ra đáp án là số nguyên duy nhất.

Example

Input

2 2 7
5 3
1 6

Output

24

Note

Ta có các cách chọn sau:

Chọn ~a_1~, ~b_1~ có giá tiền là ~min(5 + 1, 7)~ = ~6~. Chọn ~a_1~, ~b_2~ có giá tiền là ~min(5 + 6, 7)~ = ~7~. Chọn ~a_2~, ~b_1~ có giá tiền là ~min(3 + 1, 7)~ = ~4~. Chọn ~a_2~, ~b_2~ có giá tiền là ~min(3 + 6, 7)~ = ~7~.

Vậy ta có tổng tiền là ~6 + 7 + 4 + 7~ = ~24~.

DoMixi và HakyFood qua nhà ông chơi. Ông chia cho hai đứa rất nhiều kẹo.

HakyFood được ông giao nhiệm vụ chia kẹo. Ban đầu có ~n~ gói kẹo, mỗi gói chứa lượng kẹo nào đó. HakyFood đang có ~k~ cái hộp, mỗi hộp có thể cho lượng kẹo bất kỳ vào đó nhưng chỉ được chứa kẹo của một gói duy nhất. Hộp cũng có thể không chứa kẹo.

HakyFood phải chia DoMixi ~k/2~ hộp kẹo có nhiều kẹo nhất mà cậu đã chia. DoMixi có thể được chia nhiều kẹo hơn.

HakyFood rất thích kẹo nên muốn chia để sao cho lượng kẹo của cậu là lớn nhất có thể mà vẫn đảm bảo chia đúng quy tắc. Các bạn hãy giúp HakyFood nhé!

Input

Dòng đầu chứa hai số nguyên ~n, k~ (~1 \le n, k \le 10^3~, k chẵn)   – Số lượng gói kẹo và số lượng cái hộp.

Dòng tiếp theo chứa ~n~ số nguyên ~c_i~ (~1 \le c_i \le 10^3~)  – Mô tả số kẹo ở gói kẹo thứ ~i~.

Output

In ra số nguyên duy nhất là đáp án của bài.

Example

Input

4 4
5 9 6 4

Output

9

Note

Ở test ví dụ, HakyFood sẽ chia gói thứ ~2~ vào ~2~ hộp chứa ~5~ và ~4~, gói thứ ~3~ vào ~1~ hộp chứa ~5~ và gói ~1~ vào ~1~ hộp chứa ~5~. DoMixi sẽ được ~10~ cái kẹo còn HakyFood sẽ được ~9~ cái kẹo.

Anh DoMixi có một khu tổ hợp MixiSchool cực lớn với ~N~ ngôi trường phục vụ cho việc học tập của anh em MixiCon (~1 \le N \le 10^5~), trong đó một số đã được sơn và một số chưa. Anh DoMixi muốn sơn các trường còn lại để tất cả các trường đều được sơn, nhưng anh chỉ có ba màu sơn các loại từ ~1~ đến ~3~ . Hơn nữa, các anh em sẽ bối rối nếu hai trường có thể đi trực tiếp đến nhau lại cùng đè tem à nhầm cùng màu, vì vậy anh muốn đảm bảo tình huống này không xảy ra.

Đảm bảo rằng các kết nối giữa ~N~ ngôi trường không tạo thành bất kỳ 'chu trình' nào. Tức là, giữa bất kỳ hai ngôi trường nào, có tối đa một cách đi từ nơi này đến nơi kia.

Có bao nhiêu cách anh DoMixi có thể sơn các ngôi trường còn lại?

Đầu vào

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~0 \le K \le N~), lần lượt là số ngôi trường và số ngôi trường đã được sơn.

~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x~ và ~y~ (~1 \le x, y \le N, x \ne y~) mô tả một đường đi trực tiếp nối ngôi trường ~x~ và ~y~.

~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~b~ và ~c~ (~1 \le b \le N, 1 \le c \le 3~) cho biết ngôi trường ~b~ được sơn với màu ~c~.

Đầu ra

Tính số cách hợp lệ để sơn các ngôi trường còn lại, lấy phần dư modulo ~10^9+7~, sao cho không có hai ngôi trường nào được kết nối trực tiếp có cùng màu.

Example

Input

4 1
1 2
1 3
1 4
4 3

Output

8