12962번 - 나무 자르기

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

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

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

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

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

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

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

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

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

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

• 1 ≤ N, M ≤ 150
• 0 ≤ H[i], A[i] ≤ 10,000
• 0 ≤ D[i] ≤ 10,000
• 1 ≤ T ≤ 150

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

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