아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

나무 자르기

시간 제한2초메모리 제한512 MB

요약
각 저녁에 서로 다른 기계 M개로 최대 M그루를 정확히 D_i 미터로 자를 수 있을 때, T일 뒤 나무 높이 합의 최솟값을 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

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

입력

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

둘째 줄에 H1,H2,…,HNH_1, H_2, \ldots, H_N이 공백으로 구분되어 주어진다.

셋째 줄에 A1,A2,…,ANA_1, A_2, \ldots, A_N이 공백으로 구분되어 주어진다.

넷째 줄에 D1,D2,…,DMD_1, D_2, \ldots, D_M이 공백으로 구분되어 주어진다.

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

출력

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

제한

  • 1≤N,M≤1501 \le N, M \le 150
  • 0≤Hi,Ai≤100000 \le H_i, A_i \le 10000
  • 0≤Di≤100000 \le D_i \le 10000
  • 1≤T≤1501 \le T \le 150

힌트

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

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

예제5

  1. 예제 1

    입력
    2 1
4 7
7 1
7
1
    예상 출력
    15

  2. 예제 2

    입력
    3 3
3 1 2
1 1 1
7 7 7
2
    예상 출력
    12

  3. 예제 3

    입력
    2 3
100 50
75 30
200 100 50
2
    예상 출력
    130

  4. 예제 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
    예상 출력
    96

  5. 예제 5

    입력
    4 6
35 45 32 8
2 25 31 5
29 28 3 11 28 37
8
    예상 출력
    29