수빈이는 정원에 나무 N개를 가지고 있다. i번째 나무의 높이는 H[i]미터 이다. 나무는 매일 아침 A[i]미터 만큼 자란다.</p>

수빈이는 나무를 자르는 기계를 M개 가지고 있다. i번째 기계는 D[i]보다 큰 높이를 가진 나무 하나의 높이를 D[i]미터로 자른다.

수빈이는 매일 저녁마다 일부 나무를 골라서(고르지 않아도 된다) 나무를 자른다. 이때, 아래와 같은 두 조건을 만족해야 한다.

• 모든 나무는 하루에 최대 1번 잘릴 수 있다.
• 모든 기계는 하루에 최대 1번 사용할 수 있다.

총 T일이 지났을 때, 가능한 나무 높이의 합의 최솟값을 구하는 프로그램을 작성하시오. 

입력 형식

첫째 줄에 나무의 개수 N과 기계의 개수 M이 주어진다.</p>

둘째에는 H[i]가, 셋째 줄에는 A[i]가 주어진다.

넷째 줄에는 D[i]가 주어진다.

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

출력 형식

총 T일이 지났을 때, 가능한 나무 높이의 합의 최솟값을 출력한다.

예제 입력 1

2 1
4 7
7 1
7
1

예제 출력 1

15

예제 입력 2

3 3
3 1 2
1 1 1
7 7 7
2

예제 출력 2

12

예제 입력 3

2 3
100 50
75 30
200 100 50
2

예제 출력 3

130

예제 입력 4

12 4
7 10 1 7 5 4 11 5 7 9 10 8
1 3 4 10 2 1 6 4 8 7 5 10
7 1 5 10
3

예제 출력 4

96

예제 입력 5

4 6
35 45 32 8
2 25 31 5
29 28 3 11 28 37
8

예제 출력 5

29

힌트

나무 2개가 있다. 나무 1은 높이가 4미터이고, 하루에 7미터씩 자란다. 나무 2는 높이가 7미터이고, 하루에 1미터씩 자란다.</p>

첫 날 나무 1의 높이는 4+7 = 11미터, 나무 2의 높이는 7+1 = 8미터이다. 나무 1을 기계를 이용해서 잘라서 7미터로 만든다.