<p>You are the owner of a company that creates alloys using various types of metals. There are <code>n</code> different types of metals available, and you have access to <code>k</code> machines that can be used to create alloys. Each machine requires a specific amount of each metal type to create an alloy.</p>

<p>For the <code>i<sup>th</sup></code> machine to create an alloy, it needs <code>composition[i][j]</code> units of metal of type <code>j</code>. Initially, you have <code>stock[i]</code> units of metal type <code>i</code>, and purchasing one unit of metal type <code>i</code> costs <code>cost[i]</code> coins.</p>

<p>Given integers <code>n</code>, <code>k</code>, <code>budget</code>, a <strong>1-indexed</strong> 2D array <code>composition</code>, and <strong>1-indexed</strong> arrays <code>stock</code> and <code>cost</code>, your goal is to <strong>maximize</strong> the number of alloys the company can create while staying within the budget of <code>budget</code> coins.</p>

<p><strong>All alloys must be created with the same machine.</strong></p>

<p>Return <em>the maximum number of alloys that the company can create</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> It is optimal to use the 1<sup>st</sup> machine to create alloys.
To create 2 alloys we need to buy the:
- 2 units of metal of the 1<sup>st</sup> type.
- 2 units of metal of the 2<sup>nd</sup> type.
- 2 units of metal of the 3<sup>rd</sup> type.
In total, we need 2 * 1 + 2 * 2 + 2 * 3 = 12 coins, which is smaller than or equal to budget = 15.
Notice that we have 0 units of metal of each type and we have to buy all the required units of metal.
It can be proven that we can create at most 2 alloys.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
<strong>Output:</strong> 5
<strong>Explanation:</strong> It is optimal to use the 2<sup>nd</sup> machine to create alloys.
To create 5 alloys we need to buy:
- 5 units of metal of the 1<sup>st</sup> type.
- 5 units of metal of the 2<sup>nd</sup> type.
- 0 units of metal of the 3<sup>rd</sup> type.
In total, we need 5 * 1 + 5 * 2 + 0 * 3 = 15 coins, which is smaller than or equal to budget = 15.
It can be proven that we can create at most 5 alloys.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
<strong>Output:</strong> 2
<strong>Explanation:</strong> It is optimal to use the 3<sup>rd</sup> machine to create alloys.
To create 2 alloys we need to buy the:
- 1 unit of metal of the 1<sup>st</sup> type.
- 1 unit of metal of the 2<sup>nd</sup> type.
In total, we need 1 * 5 + 1 * 5 = 10 coins, which is smaller than or equal to budget = 10.
It can be proven that we can create at most 2 alloys.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n, k &lt;= 100</code></li>
	<li><code>0 &lt;= budget &lt;= 10<sup>8</sup></code></li>
	<li><code>composition.length == k</code></li>
	<li><code>composition[i].length == n</code></li>
	<li><code>1 &lt;= composition[i][j] &lt;= 100</code></li>
	<li><code>stock.length == cost.length == n</code></li>
	<li><code>0 &lt;= stock[i] &lt;= 10<sup>8</sup></code></li>
	<li><code>1 &lt;= cost[i] &lt;= 100</code></li>
</ul>

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        """
        So you have k different machines

        And for each machine, it requires a certain amount of each metal for an alloy

        You start off with stock[i] for each metal, and it costs cost[i] to bnuy a metal

        You want to choose the right machine that will make the maximum amount of metal

        Ok, let's saw we are trying machine i. The amount array create an alloy is composition[i]

        So we create as much alloy as we can with our current stock. Then, the question remains how to
        spend our money so we can make as much metal as possible.

        idea: binary search on the maximum number alloys we can make with our budget

        Can we make x alloys using our budget?
        We need a of metal 1, b of metal 2, c of metal 3...
        Just see if we have enough money to buy it in like O(n)
        So what is the maximum amount of alloys you can make? Let's just say it's budget

        So total TC is O(k*n*log(budget))
        """

        def can_make_alloys(x, metalAmounts):
            amountNeeded = [0] * n
            for i in range(n):
                amountNeeded[i] = max(x * metalAmounts[i] - stock[i], 0)
            
            totalCost = 0
            for i in range(n):
                totalCost += amountNeeded[i] * cost[i]
            
            return totalCost <= budget
            
        res = 0
        INF = 10 ** 20 
        for i in range(k):
            metalAmounts = composition[i]

            l,r = 0, budget + max(stock)

            while l <= r:
                mid = (l+r)//2
                if can_make_alloys(mid, metalAmounts):
                    l = mid + 1
                else:
                    r = mid - 1
            
            res = max(res, r)
    
        return res
            



589