리사는 레스토랑에서 웨이트리스로 일하고 있습니다. 오늘은 리사의 생일이라서 그녀는 주방장에게 그녀의 친구들을 위한 특식을 만들어 달라고 부탁하였습니다.

주방장의 음식은 N개의 재료로 이루어져 있습니다. 주방장이 1인분을 만들때마다 일정한 양의 재료가 필요합니다.

주방에는 음식에 필요한 재료가 있지만 리사는 주변 가게에서 재료를 더 사려고 합니다. 가게에는 필요한 재료를 작은 포장과 큰 포장으로 팔고 있습니다.

리사는 주방장이 가능한한 음식을 많이 만들수 있게 M 달러를 모두 써서 재료를 사려고 합니다.

입력

• 첫번째 줄은 N과 M을 입력합니다. N은 필요한 재료의 종류수, 그리고 M은 Lisa가 가지고 있는 돈입니다. 각각의 N당 6개의 정보를 입력합니다.
  • X, 10 ≤ X ≤ 100, 주방장이 하나의 음식을 만들때 필요한 재료의 양을 입력합니다.
  • Y, 1 ≤ Y ≤ 100, 지금 주방에 이용가능한 재료의 갯수를 입력합니다.
  • SM, 1 ≤ SM < 100, 가게에 있는 그 재료의 smaller package가 얼마나 많은 재료를 담고 있는지 입력합니다. (6을 입력하면 1package당 6개를 담고 있다는 뜻)
  • PM, 10 ≤ PM < 100, smaller package의 가격을 입력합니다.
  • SV , SM < SV ≤ 100, 가게에 있는 그 재료의 larger package가 얼마나 많은 재료를 담고 있는지 입력합니다.
  • PV , PM < PV ≤ 100, larger package의 가격을 입력합니다.

출력

입출력 예

input  

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

output  

5  

input  

3 65  
10 5 7 10 13 14  
10 5 8 11 14 15  
10 5 9 12 15 16  

output  

2  

첫번째 예에서 Lisa는 100달러 중 99달러로 첫번째 재료가 담긴 3개의 작은 상자와 한개의 큰상자를,  

두번째 재료가 담긴 한개의 작은 상자와 두개의 큰 상자를 샀습니다.(3·10 + 1·11 + 1·10 + 2·24 = 99).  

주방장은 첫번째 재료를 51개 가지고 있고 두번째 재료를 60개 가지고 있으므로 

총 5인분의 음식을 만들 수 있습니다. 

There are some ingredients already available in the kitchen and Lisa will buy the rest at the grocery store. The store has all the necessary ingredients, each coming in smaller and larger packages. Lisa has M dollars and wants to spend them so that the chef can make the most servings of his meal.

입력

• X, 10 ≤ X ≤ 100, the amount of the ingredient needed in one serving;
• Y, 1 ≤ Y ≤ 100, the amount of the ingredient already available in the kitchen;
• SM, 1 ≤ SM < 100, the size of the smaller package at the store;
• PM, 10 ≤ PM < 100, the price of the smaller package;
• SV , SM < SV ≤ 100, the size of the larger package; and
• PV , PM < PV ≤ 100, the price of the larger package.

출력

입출력 예

input 

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

output 

5 

input 

3 65 
10 5 7 10 13 14 
10 5 8 11 14 15 
10 5 9 12 15 16 

output 

2 

In the first example, for 99 dollars Lisa will buy three smaller and one larger package of the first 
ingredient, as well as one smaller and two larger packages of the second ingredient (3·10 + 1·11 + 1·10 
+ 2·24 = 99). 
The chef will then have 51 units (8 + 3·10 + 1·13) of the first ingredient and 60 units (20 + 1·6 + 2·17) 
of the second ingredient, enough for 5 servings. 

출처:2007-2008/regional
번역:ironamor