시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 371 104 60 24.691%

문제

효진이는 돈이 매우 많은 대학생이다. 어느 날, 효진이가 열심히 공부한 과목의 교수가 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달러를 적절히 써서 만들 수 있는 폭탄의 최대 개수를 출력한다.

예제 입력 1

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

예제 출력 1

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개의 폭탄을 만들 수 있다.

W3sicHJvYmxlbV9pZCI6IjI5NzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWQwYzRcdWM4MWNcdWM4NzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDZhOFx1YzljNFx1Yzc3NFx1YjI5NCBcdWIzYzhcdWM3NzQgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc0MCBcdWIzMDBcdWQ1NTlcdWMwZGRcdWM3NzRcdWIyZTQuIFx1YzViNFx1YjI5MCBcdWIwYTAsIFx1ZDZhOFx1YzljNFx1Yzc3NFx1YWMwMCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVhY2Y1XHViZDgwXHVkNTVjIFx1YWNmY1x1YmFhOVx1Yzc1OCBcdWFkNTBcdWMyMThcdWFjMDAgRlx1ZDU1OVx1YzgxMFx1Yzc0NCBcdWM4ZmNcdWFjYTBcdWIyZTRcdWFjZTAgJiMzOTtcdWIxOGRcdWIyZjQmIzM5O1x1Yzc0NCBcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWQ2YThcdWM5YzRcdWM3NzRcdWIyOTQgXHVkNjU0XHVhYzAwIFx1YjA5OFx1YzExYyBcdWQzZWRcdWQwYzRcdWM3NDQgXHViOWM4XHVhZDZjIFx1YjljY1x1YjRlNFx1YzViNFx1YjBiNCBcdWQ2YThcdWM5YzRcdWM3NzRcdWFjMDAgXHVjMThjXHVjNzIwXHVkNTVjIFx1YWMxY1x1Yzc3OFx1YzE4Y1x1YzcyMFx1Yzc1OCBcdWMxMmNcdWM1ZDAgXHViYjM0XHVjYzI4XHViY2M0IFx1ZDNlZFx1ZDMwY1x1Yjk3YyBcdWFjMDBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiAoXHVkNmE4XHVjOWM0XHVjNzc0XHViMjk0IFx1ZDNjOVx1ZDY1NFx1Yjk3YyBcdWMwYWNcdWI3OTFcdWQ1NThcdWJiYzBcdWI4NWMgXHViMzAwXHVkNTU5XHVhZDUwXHViOTdjIFx1ZDNlZFx1ZDMwY1x1ZDU1OFx1YzljNCBcdWM1NGFcdWIyOTRcdWIyZTQuKSBcdWQzZWRcdWQwYzRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1ZDZhOFx1YzljNFx1YmQwNFx1YmMxNFx1Yzc3NFx1YjJlNC4gXHVkNmE4XHVjOWM0XHViZDA0XHViYzE0XHViMjk0IE5cdWFjMWNcdWM3NTggXHViZDgwXHVkNDg4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YWNlMCwgXHVkNmE4XHVjOWM0XHViZDA0XHViYzE0XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMjAgXHVhYzAxIFx1YmQ4MFx1ZDQ4OFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNmE4XHVjOWM0XHVjNzc0XHVjNzU4IFx1YmU0NFx1YmMwMFx1Y2MzZFx1YWNlMFx1YzVkMFx1YjI5NCBcdWM3MDRcdWM3NTggXHViZDgwXHVkNDg4XHViNGU0XHVjNzc0IFx1Yzc3Y1x1YmQ4MCBcdWJjZjRcdWFkMDBcdWIzZmNcdWM3ODhcdWIyZTQuIFx1ZDZhOFx1YzljNFx1Yzc3NFx1YjI5NCBNXHViMmVjXHViN2VjXHViODVjIFx1YzU1NFx1YzJkY1x1YzdhNVx1YzVkMCBcdWFjMDBcdWMxMWMgXHViZDgwXHVkNDg4XHViNGU0XHVjNzQ0IFx1YjM1NCBcdWMwYWNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM1NTRcdWMyZGNcdWM3YTVcdWM1ZDQgXHVjNWM2XHViMjk0IFx1YmQ4MFx1ZDQ4OFx1Yzc3NCBcdWM1YzZcdWFjZTAsIFx1YzE4Y1x1YmU0NFx1Yzc5MFx1Yzc1OCBcdWMxMjBcdWQwZGRcdWM3NDQgXHVjODc0XHVjOTExXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDEgXHViZDgwXHVkNDg4XHViOWM4XHViMmU0IFx1YzE4Y1x1ZDYxNSBcdWQzMjhcdWQwYTRcdWM5YzBcdWM2NDAgXHViMzAwXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMFx1YWMwMCBcdWM5MDBcdWJlNDRcdWIzZmNcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDZhOFx1YzljNFx1Yzc3NFx1YjI5NCBNXHViMmVjXHViN2VjXHViODVjIFx1YmQ4MFx1ZDQ4OFx1YjRlNFx1Yzc0NCBcdWMwYWMsIFx1ZDNlZFx1ZDBjNFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAwKVx1YWNmYyBNKDEgJmxlOyBNICZsZTsgMTAwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHViZDgwXHVkNDg4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IDZcdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+WCgxMCAmbGU7IFggJmxlOyAxMDApLCBcdWQzZWRcdWQwYzQgXHVkNTVjIFx1YWMxY1x1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNTc0XHViMmY5IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9saT5cclxuXHQ8bGk+WSgxICZsZTsgWSAmbGU7IDEwMCksIFx1ZDZhOFx1YzljNFx1Yzc3NFx1Yzc1OCBcdWJlNDRcdWJjMDBcdWNjM2RcdWFjZTBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU3NFx1YjJmOSBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4PFwvbGk+XHJcblx0PGxpPlM8c3ViPk08XC9zdWI+KDEgJmxlOyBTPHN1Yj5NPFwvc3ViPiAmbHQ7IDEwMCksIFx1YzE4Y1x1ZDYxNSBcdWQzMjhcdWQwYTRcdWM5YzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9saT5cclxuXHQ8bGk+UDxzdWI+TTxcL3N1Yj4oMTAgJmxlOyBQPHN1Yj5NPFwvc3ViPiAmbHQ7IDEwMCksIFx1YzE4Y1x1ZDYxNSBcdWQzMjhcdWQwYTRcdWM5YzBcdWM3NTggXHVhYzAwXHVhY2E5PFwvbGk+XHJcblx0PGxpPlM8c3ViPlY8XC9zdWI+KFM8c3ViPk08XC9zdWI+ICZsdDsgUzxzdWI+VjxcL3N1Yj4gJmxlOyAxMDApLCBcdWIzMDBcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4PFwvbGk+XHJcblx0PGxpPlA8c3ViPlY8XC9zdWI+KFA8c3ViPk08XC9zdWI+Jmx0OyBQPHN1Yj5WPFwvc3ViPiAmbGU7IDEwMCksIFx1YjMwMFx1ZDYxNSBcdWQzMjhcdWQwYTRcdWM5YzBcdWM3NTggXHVhYzAwXHVhY2E5PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ2YThcdWM5YzRcdWM3NzRcdWFjMDAgTVx1YjJlY1x1YjdlY1x1Yjk3YyBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjMzY4XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDNlZFx1ZDBjNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIDk5XHViMmVjXHViN2VjXHViODVjIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWJkODBcdWQ0ODhcdWM3NTggXHVjMThjXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMCAzXHVhYzFjXHVjNjQwIFx1YjMwMFx1ZDYxNSBcdWQzMjhcdWQwYTRcdWM5YzAgMVx1YWMxY1x1Yjk3YywgXHViNDUwXHViYzg4XHVjOWY4IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWMxOGNcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwIDFcdWFjMWNcdWM2NDAgXHViMzAwXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMCAyXHVhYzFjXHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAoMyZtaWRkb3Q7MTAgKyAxJm1pZGRvdDsxMSArIDEmbWlkZG90OzEwICsgMiZtaWRkb3Q7MjQgPSA5OSk8XC9wPlxyXG5cclxuPHA+XHViZTQ0XHViYzAwXHVjYzNkXHVhY2UwXHVjNWQwXHViMjk0IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWJkODBcdWQ0ODhcdWM3NzQgNTFcdWFjMWMgKDggKyAzJm1pZGRvdDsxMCArIDEmbWlkZG90OzEzKSwgXHViNDUwXHViYzg4XHVjOWY4IFx1YmQ4MFx1ZDQ4OFx1Yzc3NCA2MFx1YWMxYyAoMjAgKyAxJm1pZGRvdDs2ICsgMiZtaWRkb3Q7MTcpIFx1Yzc4OFx1YWM4YyBcdWI0MThcdWFjZTAgXHVjZDFkIDVcdWFjMWNcdWM3NTggXHVkM2VkXHVkMGM0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktVSEFSIiwiZGVzY3JpcHRpb24iOiI8cD5MaXNhIHdvcmtzIGFzIGEgd2FpdHJlc3MgaW4gYSByZXN0YXVyYW50LiBUb25pZ2h0IGlzIGhlciBiaXJ0aGRheSBzbyBMaXNhIGFza2VkIHRoZSBjaGVmIHRvIHByZXBhcmUgaGlzIHNwZWNpYWwgbWVhbCBmb3IgaGVyIGZyaWVuZHMuIFRoZSBjaGVmJiMzOTtzIG1lYWwgaXMgbWFkZSBvZiBOIGluZ3JlZGllbnRzLiBUbyBwcmVwYXJlIG9uZSBzZXJ2aW5nIG9mIHRoZSBtZWFsIGhlIG5lZWRzIGEgY2VydGFpbiBhbW91bnQgb2YgZWFjaCBpbmdyZWRpZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgc29tZSBpbmdyZWRpZW50cyBhbHJlYWR5IGF2YWlsYWJsZSBpbiB0aGUga2l0Y2hlbiBhbmQgTGlzYSB3aWxsIGJ1eSB0aGUgcmVzdCBhdCB0aGUgZ3JvY2VyeSBzdG9yZS4gVGhlIHN0b3JlIGhhcyBhbGwgdGhlIG5lY2Vzc2FyeSBpbmdyZWRpZW50cywgZWFjaCBjb21pbmcgaW4gc21hbGxlciBhbmQgbGFyZ2VyIHBhY2thZ2VzLiBMaXNhIGhhcyBNIGRvbGxhcnMgYW5kIHdhbnRzIHRvIHNwZW5kIHRoZW0gc28gdGhhdCB0aGUgY2hlZiBjYW4gbWFrZSB0aGUgbW9zdCBzZXJ2aW5ncyBvZiBoaXMgbWVhbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNLCAxICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IE0gJmxlOyAxMDAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIDYgcG9zaXRpdmUgaW50ZWdlcnMsIGluZm9ybWF0aW9uIGFib3V0IG9uZSBpbmdyZWRpZW50LiBUaGVzZSBzcGVjaWZ5LCBpbiBvcmRlcjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5YLCAxMCAmbGU7IFggJmxlOyAxMDAsIHRoZSBhbW91bnQgb2YgdGhlIGluZ3JlZGllbnQgbmVlZGVkIGluIG9uZSBzZXJ2aW5nOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5ZLCAxICZsZTsgWSAmbGU7IDEwMCwgdGhlIGFtb3VudCBvZiB0aGUgaW5ncmVkaWVudCBhbHJlYWR5IGF2YWlsYWJsZSBpbiB0aGUga2l0Y2hlbjsmbmJzcDs8XC9saT5cclxuXHQ8bGk+UzxzdWI+TTxcL3N1Yj4sIDEgJmxlOyBTPHN1Yj5NPFwvc3ViPiAmbHQ7IDEwMCwgdGhlIHNpemUgb2YgdGhlIHNtYWxsZXIgcGFja2FnZSBhdCB0aGUgc3RvcmU7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlA8c3ViPk08XC9zdWI+LCAxMCAmbGU7IFA8c3ViPk08XC9zdWI+ICZsdDsgMTAwLCB0aGUgcHJpY2Ugb2YgdGhlIHNtYWxsZXIgcGFja2FnZTsmbmJzcDs8XC9saT5cclxuXHQ8bGk+UzxzdWI+VjxcL3N1Yj4sIFM8c3ViPk08XC9zdWI+ICZsdDsgUzxzdWI+VjxcL3N1Yj4gJmxlOyAxMDAsIHRoZSBzaXplIG9mIHRoZSBsYXJnZXIgcGFja2FnZTsgYW5kJm5ic3A7PFwvbGk+XHJcblx0PGxpPlA8c3ViPlY8XC9zdWI+LCBQPHN1Yj5NPFwvc3ViPiAmbHQ7IFA8c3ViPlY8XC9zdWI+ICZsZTsgMTAwLCB0aGUgcHJpY2Ugb2YgdGhlIGxhcmdlciBwYWNrYWdlLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsYXJnZXN0IG51bWJlciBvZiBzZXJ2aW5ncyB0aGUgY2hlZiBjYW4gbWFrZSBpZiBMaXNhIHNwZW5kcyBoZXIgbW9uZXkgd2lzZWx5LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZXhhbXBsZSwgZm9yIDk5IGRvbGxhcnMgTGlzYSB3aWxsIGJ1eSB0aHJlZSBzbWFsbGVyIGFuZCBvbmUgbGFyZ2VyIHBhY2thZ2Ugb2YgdGhlIGZpcnN0IGluZ3JlZGllbnQsIGFzIHdlbGwgYXMgb25lIHNtYWxsZXIgYW5kIHR3byBsYXJnZXIgcGFja2FnZXMgb2YgdGhlIHNlY29uZCBpbmdyZWRpZW50ICgzJm1pZGRvdDsxMCArIDEmbWlkZG90OzExICsgMSZtaWRkb3Q7MTAgKyAyJm1pZGRvdDsyNCA9IDk5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNoZWYgd2lsbCB0aGVuIGhhdmUgNTEgdW5pdHMgKDggKyAzJm1pZGRvdDsxMCArIDEmbWlkZG90OzEzKSBvZiB0aGUgZmlyc3QgaW5ncmVkaWVudCBhbmQgNjAgdW5pdHMgKDIwICsgMSZtaWRkb3Q7NiArIDImbWlkZG90OzE3KSBvZiB0aGUgc2Vjb25kIGluZ3JlZGllbnQsIGVub3VnaCBmb3IgNSBzZXJ2aW5ncy4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==