폭탄 만들기

효진이는 폭탄 하나를 만들 때마다 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개 만들 수 있다.