시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 375 105 61 24.696%

문제

효진이는 돈이 매우 많은 대학생이다. 어느 날, 효진이가 열심히 공부한 과목의 교수가 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+XHVkNmE4XHVjOWM0XHVjNzc0XHVjNzU4IFx1YmU0NFx1YmMwMFx1Y2MzZFx1YWNlMFx1YzVkMFx1YjI5NCBcdWM3MDRcdWM3NTggXHViZDgwXHVkNDg4XHViNGU0XHVjNzc0IFx1Yzc3Y1x1YmQ4MCBcdWJjZjRcdWFkMDBcdWIzZmNcdWM3ODhcdWIyZTQuIFx1ZDZhOFx1YzljNFx1Yzc3NFx1YjI5NCBNXHViMmVjXHViN2VjXHViODVjIFx1YzU1NFx1YzJkY1x1YzdhNVx1YzVkMCBcdWFjMDBcdWMxMWMgXHViZDgwXHVkNDg4XHViNGU0XHVjNzQ0IFx1YjM1NCBcdWMwYWNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM1NTRcdWMyZGNcdWM3YTVcdWM1ZDQgXHVjNWM2XHViMjk0IFx1YmQ4MFx1ZDQ4OFx1Yzc3NCBcdWM1YzZcdWFjZTAsIFx1YzE4Y1x1YmU0NFx1Yzc5MFx1Yzc1OCBcdWMxMjBcdWQwZGRcdWM3NDQgXHVjODc0XHVjOTExXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDEgXHViZDgwXHVkNDg4XHViOWM4XHViMmU0IFx1YzE4Y1x1ZDYxNSBcdWQzMjhcdWQwYTRcdWM5YzBcdWM2NDAgXHViMzAwXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMFx1YWMwMCBcdWM5MDBcdWJlNDRcdWIzZmNcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDZhOFx1YzljNFx1Yzc3NFx1YjI5NCBNXHViMmVjXHViN2VjXHViODVjIFx1YmQ4MFx1ZDQ4OFx1YjRlNFx1Yzc0NCBcdWMwYWMsIFx1ZDNlZFx1ZDBjNFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwMClcdWFjZmMgTSgxICZsZTsgTSAmbGU7IDEwMDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1YmQ4MFx1ZDQ4OCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCA2XHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlgoMTAgJmxlOyBYICZsZTsgMTAwKSwgXHVkM2VkXHVkMGM0IFx1ZDU1YyBcdWFjMWNcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDU3NFx1YjJmOSBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4PFwvbGk+XHJcblx0PGxpPlkoMSAmbGU7IFkgJmxlOyAxMDApLCBcdWQ2YThcdWM5YzRcdWM3NzRcdWM3NTggXHViZTQ0XHViYzAwXHVjYzNkXHVhY2UwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHViZDgwXHVkNDg4XHVjNzU4IFx1YWMxY1x1YzIxODxcL2xpPlxyXG5cdDxsaT5TPHN1Yj5NPFwvc3ViPigxICZsZTsgUzxzdWI+TTxcL3N1Yj4gJmx0OyAxMDApLCBcdWMxOGNcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4PFwvbGk+XHJcblx0PGxpPlA8c3ViPk08XC9zdWI+KDEwICZsZTsgUDxzdWI+TTxcL3N1Yj4gJmx0OyAxMDApLCBcdWMxOGNcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwXHVjNzU4IFx1YWMwMFx1YWNhOTxcL2xpPlxyXG5cdDxsaT5TPHN1Yj5WPFwvc3ViPihTPHN1Yj5NPFwvc3ViPiAmbHQ7IFM8c3ViPlY8XC9zdWI+ICZsZTsgMTAwKSwgXHViMzAwXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViZDgwXHVkNDg4XHVjNzU4IFx1YWMxY1x1YzIxODxcL2xpPlxyXG5cdDxsaT5QPHN1Yj5WPFwvc3ViPihQPHN1Yj5NPFwvc3ViPiZsdDsgUDxzdWI+VjxcL3N1Yj4gJmxlOyAxMDApLCBcdWIzMDBcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwXHVjNzU4IFx1YWMwMFx1YWNhOTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNmE4XHVjOWM0XHVjNzc0XHVhYzAwIE1cdWIyZWNcdWI3ZWNcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YzM2OFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQzZWRcdWQwYzRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyA5OVx1YjJlY1x1YjdlY1x1Yjg1YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWMxOGNcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwIDNcdWFjMWNcdWM2NDAgXHViMzAwXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMCAxXHVhYzFjXHViOTdjLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWMxOGNcdWQ2MTUgXHVkMzI4XHVkMGE0XHVjOWMwIDFcdWFjMWNcdWM2NDAgXHViMzAwXHVkNjE1IFx1ZDMyOFx1ZDBhNFx1YzljMCAyXHVhYzFjXHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAoMyZtaWRkb3Q7MTAgKyAxJm1pZGRvdDsxMSArIDEmbWlkZG90OzEwICsgMiZtaWRkb3Q7MjQgPSA5OSk8XC9wPlxyXG5cclxuPHA+XHViZTQ0XHViYzAwXHVjYzNkXHVhY2UwXHVjNWQwXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViZDgwXHVkNDg4XHVjNzc0IDUxXHVhYzFjICg4ICsgMyZtaWRkb3Q7MTAgKyAxJm1pZGRvdDsxMyksIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViZDgwXHVkNDg4XHVjNzc0IDYwXHVhYzFjICgyMCArIDEmbWlkZG90OzYgKyAyJm1pZGRvdDsxNykgXHVjNzg4XHVhYzhjIFx1YjQxOFx1YWNlMCBcdWNkMWQgNVx1YWMxY1x1Yzc1OCBcdWQzZWRcdWQwYzRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTc3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1VIQVIiLCJkZXNjcmlwdGlvbiI6IjxwPkxpc2Egd29ya3MgYXMgYSB3YWl0cmVzcyBpbiBhIHJlc3RhdXJhbnQuIFRvbmlnaHQgaXMgaGVyIGJpcnRoZGF5IHNvIExpc2EgYXNrZWQgdGhlIGNoZWYgdG8gcHJlcGFyZSBoaXMgc3BlY2lhbCBtZWFsIGZvciBoZXIgZnJpZW5kcy4gVGhlIGNoZWYmIzM5O3MgbWVhbCBpcyBtYWRlIG9mIE4gaW5ncmVkaWVudHMuIFRvIHByZXBhcmUgb25lIHNlcnZpbmcgb2YgdGhlIG1lYWwgaGUgbmVlZHMgYSBjZXJ0YWluIGFtb3VudCBvZiBlYWNoIGluZ3JlZGllbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBzb21lIGluZ3JlZGllbnRzIGFscmVhZHkgYXZhaWxhYmxlIGluIHRoZSBraXRjaGVuIGFuZCBMaXNhIHdpbGwgYnV5IHRoZSByZXN0IGF0IHRoZSBncm9jZXJ5IHN0b3JlLiBUaGUgc3RvcmUgaGFzIGFsbCB0aGUgbmVjZXNzYXJ5IGluZ3JlZGllbnRzLCBlYWNoIGNvbWluZyBpbiBzbWFsbGVyIGFuZCBsYXJnZXIgcGFja2FnZXMuIExpc2EgaGFzIE0gZG9sbGFycyBhbmQgd2FudHMgdG8gc3BlbmQgdGhlbSBzbyB0aGF0IHRoZSBjaGVmIGNhbiBtYWtlIHRoZSBtb3N0IHNlcnZpbmdzIG9mIGhpcyBtZWFsLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0sIDEgJmxlOyBOICZsZTsgMTAwLCAxICZsZTsgTSAmbGU7IDEwMDAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgNiBwb3NpdGl2ZSBpbnRlZ2VycywgaW5mb3JtYXRpb24gYWJvdXQgb25lIGluZ3JlZGllbnQuIFRoZXNlIHNwZWNpZnksIGluIG9yZGVyOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlgsIDEwICZsZTsgWCAmbGU7IDEwMCwgdGhlIGFtb3VudCBvZiB0aGUgaW5ncmVkaWVudCBuZWVkZWQgaW4gb25lIHNlcnZpbmc7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlksIDEgJmxlOyBZICZsZTsgMTAwLCB0aGUgYW1vdW50IG9mIHRoZSBpbmdyZWRpZW50IGFscmVhZHkgYXZhaWxhYmxlIGluIHRoZSBraXRjaGVuOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5TPHN1Yj5NPFwvc3ViPiwgMSAmbGU7IFM8c3ViPk08XC9zdWI+ICZsdDsgMTAwLCB0aGUgc2l6ZSBvZiB0aGUgc21hbGxlciBwYWNrYWdlIGF0IHRoZSBzdG9yZTsmbmJzcDs8XC9saT5cclxuXHQ8bGk+UDxzdWI+TTxcL3N1Yj4sIDEwICZsZTsgUDxzdWI+TTxcL3N1Yj4gJmx0OyAxMDAsIHRoZSBwcmljZSBvZiB0aGUgc21hbGxlciBwYWNrYWdlOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5TPHN1Yj5WPFwvc3ViPiwgUzxzdWI+TTxcL3N1Yj4gJmx0OyBTPHN1Yj5WPFwvc3ViPiAmbGU7IDEwMCwgdGhlIHNpemUgb2YgdGhlIGxhcmdlciBwYWNrYWdlOyBhbmQmbmJzcDs8XC9saT5cclxuXHQ8bGk+UDxzdWI+VjxcL3N1Yj4sIFA8c3ViPk08XC9zdWI+ICZsdDsgUDxzdWI+VjxcL3N1Yj4gJmxlOyAxMDAsIHRoZSBwcmljZSBvZiB0aGUgbGFyZ2VyIHBhY2thZ2UuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHNlcnZpbmdzIHRoZSBjaGVmIGNhbiBtYWtlIGlmIExpc2Egc3BlbmRzIGhlciBtb25leSB3aXNlbHkuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBleGFtcGxlLCBmb3IgOTkgZG9sbGFycyBMaXNhIHdpbGwgYnV5IHRocmVlIHNtYWxsZXIgYW5kIG9uZSBsYXJnZXIgcGFja2FnZSBvZiB0aGUgZmlyc3QgaW5ncmVkaWVudCwgYXMgd2VsbCBhcyBvbmUgc21hbGxlciBhbmQgdHdvIGxhcmdlciBwYWNrYWdlcyBvZiB0aGUgc2Vjb25kIGluZ3JlZGllbnQgKDMmbWlkZG90OzEwICsgMSZtaWRkb3Q7MTEgKyAxJm1pZGRvdDsxMCArIDImbWlkZG90OzI0ID0gOTkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY2hlZiB3aWxsIHRoZW4gaGF2ZSA1MSB1bml0cyAoOCArIDMmbWlkZG90OzEwICsgMSZtaWRkb3Q7MTMpIG9mIHRoZSBmaXJzdCBpbmdyZWRpZW50IGFuZCA2MCB1bml0cyAoMjAgKyAxJm1pZGRvdDs2ICsgMiZtaWRkb3Q7MTcpIG9mIHRoZSBzZWNvbmQgaW5ncmVkaWVudCwgZW5vdWdoIGZvciA1IHNlcnZpbmdzLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d