나무 자르기

수빈이는 정원에서 나무 N그루를 키운다. i번째 나무의 현재 높이는 $H_i$미터이고, 매일 아침 $A_i$미터씩 자란다.

수빈이는 나무를 자르는 기계를 M대 가지고 있다. i번째 기계는 높이가 $D_i$미터보다 큰 나무 한 그루를 골라 그 높이를 정확히 $D_i$미터로 자른다. 높이가 $D_i$미터 이하인 나무에는 i번째 기계를 쓸 수 없다.

매일 저녁에 수빈이는 나무를 골라서 자른다. 한 그루도 고르지 않아도 된다. 이때 다음 두 조건을 지켜야 한다.

• 나무 한 그루는 하루에 최대 한 번 잘린다.
• 기계 한 대는 하루에 최대 한 번 쓸 수 있다.

즉 같은 날 저녁에 잘리는 나무는 서로 다른 기계와 하나씩 짝을 이룬다.

하루는 아침의 성장과 저녁의 자르기로 이루어진다. T일이 지난 뒤 나무 높이의 합으로 가능한 값 중 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 나무의 수 N과 기계의 수 M이 공백으로 구분되어 주어진다.

둘째 줄에 $H_1, H_2, \ldots, H_N$이 공백으로 구분되어 주어진다.

셋째 줄에 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다.

넷째 줄에 $D_1, D_2, \ldots, D_M$이 공백으로 구분되어 주어진다.

다섯째 줄에 T가 주어진다.

T일이 지난 뒤 나무 높이의 합으로 가능한 값 중 최솟값을 한 줄에 출력한다.

• $1 \le N, M \le 150$
• $0 \le H_i, A_i \le 10000$
• $0 \le D_i \le 10000$
• $1 \le T \le 150$

나무가 2그루 있다고 하자. 1번 나무는 높이가 4미터이고 하루에 7미터씩 자라며, 2번 나무는 높이가 7미터이고 하루에 1미터씩 자란다. 기계는 $D_1 = 7$인 것 한 대뿐이고, T는 1이다.

첫째 날 아침이 지나면 1번 나무의 높이는 $4 + 7 = 11$미터, 2번 나무의 높이는 $7 + 1 = 8$미터가 된다. 저녁에 기계로 1번 나무를 잘라 7미터로 만들면 높이의 합은 15가 되고, 이보다 작게 만들 수는 없다.