Problem Description

It is the year 20XX, and the Paken club room has acquired a feature where solving problems indoors doubles your rating. However, despite the supernatural phenomena occurring in the Paken club room, there is no way to avoid the difference in ratings among the members. One day, lamenting this fact, the Paken club leader decided to redistribute the members' ratings equally.

On the day the leader's plan is carried out, there are $ N $ members visiting the Paken club. The $ i $-th member has a rating of $ A_i $, enters the club room at time $ L_i $, and leaves the room at time $ R_i $. No members enter or leave at the same time.
The leader can subtract any integer from a member's rating when they pass through the entrance or exit of the club room, adding that amount to their own rating. However, at no point during these operations can the rating of either the member or the leader become negative.

When the leader performs the operation, the rating transition of member $ i $ is as follows, where $ E $ is the leader's rating:

• Before entering the room, the rating is $ A_i $.
• Enters the Paken club room. The leader subtracts $x\ (-E\ \leq\ x\ \leq\ A_i)$. The ratings of the leader and member $ i $ become $E+x,\ A_i-x$ respectively.
• Solves problems in the Paken club room. The rating doubles.
• Leaves the Paken club room. The leader subtracts $y\ (-E'\ \leq\ y\ \leq\ A_i')$. The ratings of the leader and member $ i $ become $E'+y,\ A_i'-y$ respectively. Here, $ E',A_i' $ are the ratings of the leader and member $ i $ at the time they leave the room.

From the start to the end of the plan, the leader's rating $ E $ does not increase or decrease except through the operations at the entrance and exit.

Your task is to find the maximum value of the "minimum rating of the members excluding the leader" after the leader has completed all operations.

Input Format

The input is given in the following format:

$N\ E$ $A_1\ A_2\ \dots\ A_{N-1}\ A_N$ $L_1\ R_1$ $L_2\ R_2$ $\vdots$ $L_N\ R_N$

Output Format

Output the value instructed in the problem statement. If the answer is $ 10^{12} $ or more, output 'inf' instead.

Sample Input and Output

Sample Input #1

2 2
1 1
1 2
3 4

Sample Output #1

4

Sample Input #2

4 2
2 3 1 3
2 4
1 7
3 8
5 6

Sample Output #2

7

Sample Input #3

6 4098
8 6 9 1 2 1
1 3
5 9
4 11
8 12
2 10
6 7

Sample Output #3

2532

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ E\ \leq\ 10^9$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $1\ \leq\ L_i\ <\ R_i\ \leq\ 2N\ (1\ \leq\ i\ \leq\ N)$
• All values of $L_i,\ R_i$ are distinct.

Partial Points

• Subtask 1 (50 points): $1\ \leq\ N\ \leq\ 4,\ 1\ \leq\ E\ \leq\ 3,\ 1\ \leq\ A_i\ \leq\ 3$
• Subtask 2 (200 points): $ R_i $
• Subtask 3 (550 points): No additional constraints.

Sample Explanation 1

At time 1: The leader gives member 1 a rating of $ 1 $. Member 1's rating becomes $ 2 $.
At time 2: Member 1 leaves with a rating of $ 4 $.
At time 3: The leader gives member 2 a rating of $ 1 $. Member 2's rating becomes $ 2 $.
At time 4: Member 2 leaves with a rating of $ 4 $.
The minimum rating of the members cannot be made $ 5 $ or more, so the minimum value is $ 4 $. This sample satisfies the constraints of Subtask 1 and 2.

Sample Explanation 2

This example satisfies the constraints of Subtask 1.

Sample Explanation 3

This example satisfies the constraints of Subtask 3.

见题面 Input 部分

见题面 Output 部分