시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 292 73 37 19.681%

문제

효진이는 돈이 매우 많은 대학생이다. 어느 날, 효진이가 열심히 공부한 과목의 교수가 F학점을 주겠다고 '농담'을 했다. 하지만 효진이는 화가 나서 폭탄을 마구 만들어내 효진이가 소유한 개인소유의 섬에 무차별 폭파를 가하기로 했다. (효진이는 평화를 사랑하므로 대학교를 폭파하진 않는다.) 폭탄의 이름은 효진봄바이다. 효진봄바는 N개의 부품으로 이루어져있고, 효진봄바를 만들기 위해선 각 부품이 여러 개 필요하다.

효진이의 비밀창고에는 위의 부품들이 일부 보관돼있다. 효진이는 M달러로 암시장에 가서 부품들을 더 사려고 한다. 암시장엔 없는 부품이 없고, 소비자의 선택을 존중하기 위해 각 부품마다 소형 패키지와 대형 패키지가 준비돼있다.

효진이는 M달러로 부품들을 사, 폭탄을 최대한 많이 만들고 싶어한다.

입력

첫번째 줄에는 정수 N(1 ≤ N ≤ 100)과 M(1 ≤ M ≤ 100000)이 주어진다.

다음 N개의 각 줄마다 부품 하나의 정보를 의미하는 6개의 양의 정수가 주어진다.

  • 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달러를 적절히 써서 만들 수 있는 폭탄의 최대 개수를 출력한다.

예제 입력

2 100
10 8 10 10 13 11
12 20 6 10 17 24

예제 출력

5

힌트

예제에서 99달러로 첫번째 부품의 소형 패키지 3개와 대형 패키지 1개를, 두번째 부품의 소형 패키지 1개와 대형 패키지 2개를 구입할 수 있다. (3·10 + 1·11 + 1·10 + 2·24 = 99)

비밀창고에는 첫번째 부품이 51개 (8 + 3·10 + 1·13), 두번째 부품이 60개 (20 + 1·6 + 2·17) 있게 되고 총 5개의 폭탄을 만들 수 있다.