<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:
        """
        [Enumeration]
        if n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3], 
        we can see it cost 1+2+3 to buy enough metal to use machine 0, it cost 1+2+30 to buy enough metal to use machine 1
        we use machine 1, then make until we run out of money
        
        n = 3, k = 2, budget = 33, composition = [[1,15,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
        we can see it cost 34 to use m0, and 33 to use m1
        we choose m0, but we cant make any alloy
        so we then choose m1, we can make 1
        
        [Inutition]
        we pick each machine
        
        take the composition of that machine and see what you need to buy to fill 1 order
        
        if you have left over buget and stock, do it again
        
        then pick a different machine and do the same. take the max alloy count
        
        [Implementation] Works but TLE
        loop through the composition
            take each composition
            while you have enough money
            set var ready = True
            set var m_diff
            loop though each metal
                find difference of what we still need to build an alloy
                if diff is positive
                    calculate money need to fill the diff
                    add that money to m_diff
                    set the stock to 0
                else
                    redeuce the stock by perscribed amount
            if diff < budget (we can afford it)
                reduce budget by diff
                count +1
            reset the res to max res
            
        [Implementation2 ] reverse the search fold binary search into the count to save runs
        
        use another function to calculate cost of building x alloy and see if you can do it
        
        
        """
#         # [Implementation] Works but TLE
        
#         res = 0
#         # loop through the composition
#         for j in range(k):
#             # take each composition
#             comp = composition[j]
#             count = 0
#             cur_stock = copy.deepcopy(stock)
#             cur_budget = budget
#             # while true
#             while True:
#                 # set var m_diff
#                 m_diff = 0
#                 # loop though each metal
#                 for i in range(n):
#                     # find difference of what we still need to build an alloy
#                     diff = cur_stock[i] - comp[i] 
#                     # if diff is negative
#                     if diff<0:
#                         # calculate money need to fill the diff
#                         # add that money to m_diff
#                         m_diff +=-diff*cost[i]
#                         # set the stock to 0
#                         cur_stock[i] = 0
#                     else:
#                         # set the stock to diff
#                         cur_stock[i] = diff
#                 # if diff < budget (we can afford it)
#                 if m_diff<=cur_budget:
#                     # reduce budget by diff
#                     cur_budget -= m_diff
#                     count +=1
#                 # else you break
#                 else:
#                     break
#             # reset the res to max res
#             res = max(res, count)
#         return res

    # create upper and lower bound for the binary search
        low, high = 0, int(1e9)
        res = 0
        while low<=high:
            mid = low + (high-low)//2
            # if we can achive the perscribed amount
            if self.calculate(mid, budget, composition, stock, cost):
                res = mid
                low = mid+1
            else:
                high = mid-1
        return res
        
    

    def calculate(self, count, budget, composition, stock, cost):
        # loop through the composition
        for j in range(len(composition)):
            # take each composition
            comp = composition[j]
            # set var m_diff
            m_diff = 0
            # loop though each metal
            for i in range(len(comp)):
                # find difference of what we still need to build perscribed count of alloy
                diff = stock[i] - comp[i]*count
                # if diff is negative
                if diff<0:
                    # calculate money need to fill the diff
                    # add that money to m_diff
                    m_diff +=-diff*cost[i]
            # if diff < budget (we can produce the perscribed count)
            if m_diff<=budget:
                return True
        return False
    
    
493