문제

M 게임에는 여러 재료 아이템들을 활용하여 새로운 아이템을 만들어 내는 기능이 구현되어 있다. 한 개의 생산물을 만들기 위해서는 어떤 재료 아이템이 각각 몇 개씩 필요한 지 미리 정의되어 있고 알려져 있다. 이를테면 철괴를 만들기 위해서는 철광석 조각이 5개 필요하다던지, 나무판 3개와 일반 옷감 3개를 사용하여 스탠딩 램프를 만들 수 있는 식이다. 한편으로 각 재료 아이템은 플레이어가 가진 가방의 각 칸에 보관되는데, 한 칸에 일정 수량씩 묶여 있는 식이다. 예를 들어, 철광석 조각이 세 칸에 각각 20, 18, 13 개씩 있을 수 있다.

이 게임에서 수 년 전까지만 하더라도 플레이어는 아이템을 여러 개 만들기 위해서 한 개의 아이템을 만들 때마다 가방에서 알맞은 재료가 들어 있는 각 칸을 지정하여 생산을 시도해야 했다. 그러나 수백 개씩 생산해야 하는 일이 흔했기 때문에 사람이 할 필요가 없는 그저 무의미한 반복 작업일 뿐이었다.

그러나 "자동 생산" 이라는 기능이 도입되면서 많은 것이 달라졌다. 이 기능을 사용하면 가방의 칸들 중에서 생산에 필요한 재료인 것들을 모두 합쳐 최대 10칸 자동으로 선택하여 주고, 그 선택된 재료들을 가지고 재료가 충분한 동안 계속해서 한 개씩 생산하기를 반복한다. 예를 들어 스탠딩 램프를 "자동 생산" 하면 나무판과 일반 옷감이 보관된 칸들이 합쳐서 10칸 이내로 자동으로 선택된 뒤 선택된 칸들의 나무판과 일반 옷감의 수를 모두 합쳐 각각 3개 이상일 동안 계속해서 생산을 반복하게 되는 것이다. 당연하게도, 자동 생산 알고리즘이 어떤 칸을 선택하느냐에 따라서 생산할 수 있는 갯수가 달라질 것이다.

어떤 아이템을 생산하기 위해 필요한 각 재료의 갯수와, 플레이어의 가방에 각 재료가 보관되어 있는 칸의 아이템 갯수가 주어질 때 자동 생산 기능을 한 차례 작동시켜 만들어낼 수 있는 최대 생산물 갯수는 몇 개인지 알아내는 프로그램을 작성하라.