All problems

Bakery Full Batches

Easy · hash map

A bakery keeps its ingredients in small jars. The list pantry has one entry per jar: the number is the ingredient's id, and each jar holds exactly one portion. Two jars with the same id hold the same ingredient.

One batch of a recipe needs several ingredients. The recipe is given as two lists of equal length: ingredient items[k] is needed in amounts[k] portions. The ids in items are all different.

Every jar can be used for at most one batch (a portion is used up once). Return the largest number of complete batches the bakery can bake from its pantry. If some needed ingredient is missing, the answer is 0.

Examples

Example 1

Input: pantry = [4, 4, 4, 4, 7, 7, 9], items = [4, 7], amounts = [2, 1]

Output: 2

There are four jars of 4 (two batches' worth) and two jars of 7 (two batches' worth). The jar of 9 is not needed.

Example 2

Input: pantry = [1, 2, 2, 3], items = [1, 5], amounts = [1, 1]

Output: 0

Ingredient 5 is not in the pantry.

Example 3

Input: pantry = [2, 2, 2, 2, 2], items = [2], amounts = [2]

Output: 2

Constraints

• 0 <= len(pantry) <= 10^4
• 1 <= len(items) = len(amounts) <= 10^4
• 1 <= pantry[i], items[k] <= 10^9
• 1 <= amounts[k] <= 10^4
• The ids in items are all different.