Vitaminai

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

요약
비타민 C와 D 함량 및 가격이 주어진 100개의 정제 중에서 C와 D를 각각 목표량 이상 섭취하는 최소 비용을 구한다.
난이도

어려움10점 중 8점

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

문제

Žiemos laikotarpiu svarbu pasirūpinti, kad organizmas gautų pakankamai vitaminų. Adomas, tą suprasdamas, užėjo į vaistinę „Vitaminų Pasaulis“. Ši vaistinė parduoda įvairiausias multivitaminų tabletes. Kadangi nesaikingai vartojant vitaminus galima pakenkti, vaistinė vienam pirkėjui parduoda ne daugiau kaip vieną tos pačios rūšies tabletę.

Adomą labiausiai domina vitaminas C, kuris stiprina imunitetą, ir vitaminas D, kuris labai svarbus kaulams ir dantims. Tačiau parduotuvė turi tiek daug įvairių tablečių, kad Adomas pasimetė.

Žinoma koks kiekis vitamino C ir vitamino D yra kiekvienoje tabletėje, bei nurodyta kiekvienos tabletės kaina. Raskite, kiek mažiausiai turės sumokėti Adomas, kad įsigytų bent CC miligramų vitamino C ir bent DD miligramų vitamino D.

입력

Pirmojoje eilutėje įrašyti trys sveikieji skaičiai: tablečių skaičius NN ir Adomo norimas vitaminų kiekis CC ir DD.

Tolimesnėse NN eilučių aprašytos tabletės. Kiekvienoje eilutėje įrašytas vitamino CC kiekis c_ic\_i, vitamino DD kiekis d_id\_i (miligramais), ir tabletės kaina centais k_ik\_i. Visi skaičiai yra sveikieji.

출력

Pirmojoje eilutėje išveskite vieną sveikąjį skaičių: kiek mažiausiai centų turės išleisti Adomas, kad įsigytų bent CC miligramų vitamino C, ir bent DD miligramų vitamino D.

Sprendinys visada egzistuos: nusipirkęs visas tabletes, Adomas visuomet gaus norimą kiekį vitaminų.

제한

  • 1≤N≤1001 ≤ N ≤ 100
  • 0≤c_i,C≤10,0000 ≤ c\_i , C ≤ 10\\,000
  • 0≤d_i,D≤5000 ≤ d\_i , D ≤ 500
    • 1≤k_i≤10001 ≤ k\_i ≤ 1000

예제1

  1. 예제 1

    입력
    5 300 50
100 30 50
200 10 25
100 50 100
400 0 80
0 100 200
    예상 출력
    125