Request X Chocolates

There are some children, each child having a unique id requesting different quantity of chocolate in the given order denoted by 2D matrix A of size N x 2 where A[i][0] denotes chidren id and A[i][1] denotes quantity.

A child can request any quantity of chocolate multiple times. The person distributing the chocolate has only B chocolates.

You are asked to find the maximum value of X such that each children can request a total sum of at most X chocolates and total chocolates requested by all children is not more than B.

NOTE:

1 <= N <= 10⁵

1 <= A[i][0], A[i][1], B <= 10⁹

B < Sum of all requested quantity

First argument is a 2d array A of size N x 2 denoting that A[i][0] child is requesting A[i][1] quantity of chocolate.

Second argument is an integer B denoting the total quantity of chocolates.

Return an integer denoting the maximum value of X.

Input 1:

 A = [
       [1, 2]
       [2, 1]
       [1, 4]
       [2, 9]
       [1, 1]
       [3, 2]
     ]
 B = 6

Input 2:

 A = [
       [10, 2]
       [10, 5]
       [4, 4]
       [4, 1]
     ]
 B = 1

Output 1:

 5

Output 2:

 1

Explanation 1:

 Each children can get at most 5 chocolates such that the total sum of chocolates recieved is less than 6.
 Child with id 1: will get 2 chocolates in first request. Any other request will not be fulfilled.
 Child with id 2: will get 1 chocolate in first request. Any other request will not be fulfilled.
 Child with id 3: will get 2 choclates in first request.
 Total chocolate = 5 which is less than 6.
 NOTE: We can't increase the value of X to 6. Second request of child 1 will get fulfilled at total chocolates will be greater than 6.
 

Explanation 2:

 The maximum value of X is 1.