Nhà hàng của Tom rất nổi tiếng. Một trong những lý do là mỗi món ăn đều được ít nhất \(K\) đầu bếp khác nhau cùng chế biến. Hôm nay cần chuẩn bị \(N\) món ăn, trong đó món thứ \(i\) cần \(A_i\) giờ làm việc.

Tom có thể thuê trong số \(M\) đầu bếp để chuẩn bị tất cả các món ăn, nhưng đầu bếp thứ \(j\) chỉ làm việc tối đa \(B_j\) giờ. Hơn nữa, ngay cả khi làm ít hơn, người đó vẫn muốn được trả công cho đủ \(B_j\) giờ.

Một đầu bếp có thể tham gia chế biến nhiều món với thời gian khác nhau. Tuy nhiên, một món ăn chỉ được chuẩn bị đúng yêu cầu nếu có ít nhất \(K\) đầu bếp tham gia và tổng thời gian họ làm việc cho món đó bằng đúng \(A_i\). Mỗi khi tham gia chế biến một món, một đầu bếp luôn làm việc cho món đó một số nguyên dương giờ.

Hãy giúp Tom chọn một tập đầu bếp tối ưu để tổng số giờ được trả công nhưng không làm việc là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(M\), \(K\).

Dòng thứ hai chứa \(N\) số nguyên \(A_i\). Dòng thứ ba chứa \(M\) số nguyên \(B_j\).

Dữ liệu ra

In trên một dòng số giờ các đầu bếp không làm việc nhưng vẫn được trả công khi Tom chọn tập đầu bếp cần thuê một cách tối ưu. Nếu không thể chuẩn bị tất cả \(N\) món ăn theo các quy tắc đã mô tả, in Impossible.

Ràng buộc

\(1\le N,M,K,A_i,B_j\le 300\).

Phân nhóm

1. Nhóm 1 (9 điểm): \(1\le N,K\le 300\), \(1\le M\le 2\), \(1\le A_i,B_j\le 300\).
2. Nhóm 2 (22 điểm): \(1\le N,K\le 300\), \(1\le M\le 15\), \(1\le A_i,B_j\le 300\).
3. Nhóm 3 (20 điểm): \(1\le N,M,A_i,B_j\le 300\), \(K=1\).
4. Nhóm 4 (21 điểm): \(1\le N,M,K,A_i,B_j\le 40\).
5. Nhóm 5 (28 điểm): \(1\le N,M,K,A_i,B_j\le 300\).

Ví dụ

1 2 2
5
3 4

2

1 1 2
5
5

Impossible

3 3 3
3 3 2
3 3 3

Impossible

Nguồn

Baltic Olympiad in Informatics 2019, ngày 2, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.