폭탄 만들기

시간 제한1초메모리 제한128 MB

요약
창고 재고와 소포장, 대포장 가격이 주어질 때 예산 M 이내로 최대 몇 개의 폭탄을 만들 수 있는지, 정답에 대한 이분 탐색과 부품별 최소 구매 비용 계산으로 구하는 문제입니다.
난이도

보통10점 중 7점

유형
이분 탐색, 그리디, 수학
정답자
아직 제출이 없습니다

문제

효진이는 폭탄 하나를 만들 때마다 N종류의 부품을 정해진 개수만큼 사용해야 한다. 현재 각 부품은 창고에 일부 보관되어 있으며, 부족한 부품은 예산 M달러 안에서 시장에서 추가로 살 수 있다.

각 부품은 소형 패키지와 대형 패키지 두 가지로 판매된다. 패키지는 원하는 만큼 살 수 있고, 패키지 안에 든 부품 수와 가격은 부품마다 다르다.

예산을 넘지 않고 만들 수 있는 폭탄의 최대 개수를 구하라.

입력

첫째 줄에 부품 종류 수 N과 예산 M이 주어진다 (1 <= N <= 100, 1 <= M <= 100000).

다음 N개의 줄에는 한 부품에 대한 여섯 양의 정수 X, Y, SM, PM, SV, PV가 주어진다.

  • X: 폭탄 하나를 만드는 데 필요한 해당 부품 수 (10 <= X <= 100)
  • Y: 창고에 이미 있는 해당 부품 수 (1 <= Y <= 100)
  • SM: 소형 패키지 하나에 들어 있는 부품 수 (1 <= SM < 100)
  • PM: 소형 패키지 하나의 가격 (10 <= PM < 100)
  • SV: 대형 패키지 하나에 들어 있는 부품 수 (SM < SV <= 100)
  • PV: 대형 패키지 하나의 가격 (PM < PV <= 100)

출력

효진이가 M달러 이하를 써서 만들 수 있는 폭탄의 최대 개수를 출력한다.

힌트

첫 번째 표시 테스트 케이스에서는 첫 번째 부품의 소형 패키지 3개와 대형 패키지 1개, 두 번째 부품의 소형 패키지 1개와 대형 패키지 2개를 사면 99달러가 든다.

그러면 창고에는 첫 번째 부품이 51개, 두 번째 부품이 60개 있게 되어 폭탄을 5개 만들 수 있다.

예제2

  1. 예제 1

    입력
    2 100
10 8 10 10 13 11
12 20 6 10 17 24
    예상 출력
    5

  2. 예제 2

    입력
    3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16
    예상 출력
    2