문제

과일을 사기 위해 마트를 간 플레이어는 큰 난관에 봉착했다. 왜냐하면 팔고 있는 과일이 너무 많아서, 어떤 과일을 사면 좋을지 결정하는 게 너무 어려웠기 때문이다. 현재 마트에서 팔고 있는 과일은  종류가 한 개씩 있고, 각 과일의 가격은 , 그리고 그 과일을 먹었을 때 플레이어가 얻을 수 있는 포만감은 이다.

이 마트에서는 특이하게도 과일을 조각 단위로 구매하는 것이 가능하다. 가격이 인 과일을 조각 단위로 구매하고자 할 경우, 플레이어는 이 과일을 개의 조각으로 자른 뒤 그중 원하는 몇 개의 조각만을 구매할 수 있다. 이때 모든 조각의 가격은 , 먹었을 때 얻을 수 있는 포만감은 로 동일하다.

플레이어는 만큼의 돈을 가지고 있다. 플레이어는 주어진 금액 이내에서 구매한 과일들의 포만감 합이 가장 크게 되도록 살 과일을 선택하려고 한다. 플레이어가 최적의 방법에 따라 과일을 구매했을 때, 구매한 과일들의 최대 포만감 합을 구해보자.

예제 설명

첫 번째 예제에서는 두 번째, 세 번째, 네 번째, 여섯 번째 과일을 통째로 구매하고, 첫 번째 과일을 한 조각 구매하는 것이 최대 포만감 합을 얻을 수 있는 방법이다.

입력

첫째 줄에 마트에서 파는 과일의 개수 과 플레이어가 가진 돈 가 공백을 두고 주어진다.
다음 개의 줄에는 각 과일의 가격 와 그 과일을 먹었을 때 플레이어가 얻을 수 있는 포만감 가 공백을 두고 주어진다.

• 
• 
• 
• 
• 는 항상 의 배수이다.
• 입력에서 주어지는 모든 수는 정수이다.
  

출력

플레이어가 구매한 과일들의 최대 포만감 합을 출력한다.