Problem Statement

"Pizza At", a fast food chain, offers three kinds of pizza: "A-pizza", "B-pizza" and "AB-pizza". A-pizza and B-pizza are completely different pizzas, and AB-pizza is one half of A-pizza and one half of B-pizza combined together. The prices of one A-pizza, B-pizza and AB-pizza are A yen, B yen and C yen (yen is the currency of Japan), respectively.

Nakahashi needs to prepare X A-pizzas and Y B-pizzas for a party tonight. He can only obtain these pizzas by directly buying A-pizzas and B-pizzas, or buying two AB-pizzas and then rearrange them into one A-pizza and one B-pizza. At least how much money does he need for this? It is fine to have more pizzas than necessary by rearranging pizzas.

Constraints

• 1 ≤ A, B, C ≤ 5000
• 1 ≤ X, Y ≤ 10^5
• All values in input are integers.

Sample Input 1

1500 2000 1600 3 2

Sample Output 1

7900

It is optimal to buy four AB-pizzas and rearrange them into two A-pizzas and two B-pizzas, then buy additional one A-pizza.

Sample Input 2

1500 2000 1900 3 2

Sample Output 2

8500

It is optimal to directly buy three A-pizzas and two B-pizzas.

Sample Input 3

1500 2000 500 90000 100000

Sample Output 3

100000000

It is optimal to buy 200000 AB-pizzas and rearrange them into 100000 A-pizzas and 100000 B-pizzas. We will have 10000 more A-pizzas than necessary, but that is fine.

Problem Statement

"Teishi-zushi", a Japanese restaurant, is a plain restaurant with only one round counter. The outer circumference of the counter is C meters. Customers cannot go inside the counter.

Nakahashi entered Teishi-zushi, and he was guided to the counter. Now, there are N pieces of sushi (vinegared rice with seafood and so on) on the counter. The distance measured clockwise from the point where Nakahashi is standing to the point where the i-th sushi is placed, is x_i meters. Also, the i-th sushi has a nutritive value of v_i kilocalories.

Nakahashi can freely walk around the circumference of the counter. When he reach a point where a sushi is placed, he can eat that sushi and take in its nutrition (naturally, the sushi disappears). However, while walking, he consumes 1 kilocalories per meter.

Whenever he is satisfied, he can leave the restaurant from any place (he does not have to return to the initial place). On balance, at most how much nutrition can he take in before he leaves? That is, what is the maximum possible value of the total nutrition taken in minus the total energy consumed? Assume that there are no other customers, and no new sushi will be added to the counter. Also, since Nakahashi has plenty of nutrition in his body, assume that no matter how much he walks and consumes energy, he never dies from hunger.

Constraints

• 1 ≤ N ≤ 10^5
• 2 ≤ C ≤ 10^{14}
• 1 ≤ x_1 < x_2 < ... < x_N < C
• 1 ≤ v_i ≤ 10^9
• All values in input are integers.

Subscores

• 300 points will be awarded for passing the test set satisfying N ≤ 100.

Sample Input 1

3 20
2 80
9 120
16 1

Sample Output 1

191

There are three sushi on the counter with a circumference of 20 meters. If he walks two meters clockwise from the initial place, he can eat a sushi of 80 kilocalories. If he walks seven more meters clockwise, he can eat a sushi of 120 kilocalories. If he leaves now, the total nutrition taken in is 200 kilocalories, and the total energy consumed is 9 kilocalories, thus he can take in 191 kilocalories on balance, which is the largest possible value.

Sample Input 2

3 20
2 80
9 1
16 120

Sample Output 2

192

The second and third sushi have been swapped. Again, if he walks two meters clockwise from the initial place, he can eat a sushi of 80 kilocalories. If he walks six more meters counterclockwise this time, he can eat a sushi of 120 kilocalories. If he leaves now, the total nutrition taken in is 200 kilocalories, and the total energy consumed is 8 kilocalories, thus he can take in 192 kilocalories on balance, which is the largest possible value.

Sample Input 3

1 100000000000000
50000000000000 1

Sample Output 3

0

Even though the only sushi is so far that it does not fit into a 32-bit integer, its nutritive value is low, thus he should immediately leave without doing anything.

Sample Input 4

15 10000000000
400000000 1000000000
800000000 1000000000
1900000000 1000000000
2400000000 1000000000
2900000000 1000000000
3300000000 1000000000
3700000000 1000000000
3800000000 1000000000
4000000000 1000000000
4100000000 1000000000
5200000000 1000000000
6600000000 1000000000
8000000000 1000000000
9300000000 1000000000
9700000000 1000000000

Sample Output 4

6500000000

All these sample inputs above are included in the test set for the partial score.

Problem Statement

In "Takahashi-ya", a ramen restaurant, basically they have one menu: "ramen", but N kinds of toppings are also offered. When a customer orders a bowl of ramen, for each kind of topping, he/she can choose whether to put it on top of his/her ramen or not. There is no limit on the number of toppings, and it is allowed to have all kinds of toppings or no topping at all. That is, considering the combination of the toppings, 2^N types of ramen can be ordered.

Akaki entered Takahashi-ya. She is thinking of ordering some bowls of ramen that satisfy both of the following two conditions:

• Do not order multiple bowls of ramen with the exactly same set of toppings.
• Each of the N kinds of toppings is on two or more bowls of ramen ordered.

You are given N and a prime number M. Find the number of the sets of bowls of ramen that satisfy these conditions, disregarding order, modulo M. Since she is in extreme hunger, ordering any number of bowls of ramen is fine.

Constraints

• 2 \leq N \leq 3000
• 10^8 \leq M \leq 10^9 + 9
• N is an integer.
• M is a prime number.

Subscores

• 600 points will be awarded for passing the test set satisfying N ≤ 50.

Sample Input 1

2 1000000007

Sample Output 1

2

Let the two kinds of toppings be A and B. Four types of ramen can be ordered: "no toppings", "with A", "with B" and "with A, B". There are two sets of ramen that satisfy the conditions:

• The following three ramen: "with A", "with B", "with A, B".
• Four ramen, one for each type.

Sample Input 2

3 1000000009

Sample Output 2

118

Let the three kinds of toppings be A, B and C. In addition to the four types of ramen above, four more types of ramen can be ordered, where C is added to the above four. There are 118 sets of ramen that satisfy the conditions, and here are some of them:

• The following three ramen: "with A, B", "with A, C", "with B, C".
• The following five ramen: "no toppings", "with A", "with A, B", "with B, C", "with A, B, C".
• Eight ramen, one for each type.

Note that the set of the following three does not satisfy the condition: "'with A', 'with B', 'with A, B'", because C is not on any of them.

Sample Input 3

50 111111113

Sample Output 3

1456748

Remember to print the number of the sets modulo M. Note that these three sample inputs above are included in the test set for the partial score.

Sample Input 4

3000 123456791

Sample Output 4

16369789

This sample input is not included in the test set for the partial score.

Problem Statement

Akaki, a patissier, can make N kinds of doughnut using only a certain powder called "Okashi no Moto" (literally "material of pastry", simply called Moto below) as ingredient. These doughnuts are called Doughnut 1, Doughnut 2, ..., Doughnut N. In order to make one Doughnut i (1 ≤ i ≤ N), she needs to consume m_i grams of Moto. She cannot make a non-integer number of doughnuts, such as 0.5 doughnuts.

The recipes of these doughnuts are developed by repeated modifications from the recipe of Doughnut 1. Specifically, the recipe of Doughnut i (2 ≤ i ≤ N) is a direct modification of the recipe of Doughnut p_i (1 ≤ p_i < i).

Now, she has X grams of Moto. She decides to make as many doughnuts as possible for a party tonight. However, since the tastes of the guests differ, she will obey the following condition:

• Let c_i be the number of Doughnut i (1 ≤ i ≤ N) that she makes. For each integer i such that 2 ≤ i ≤ N, c_{p_i} ≤ c_i ≤ c_{p_i} + D must hold. Here, D is a predetermined value.

At most how many doughnuts can be made here? She does not necessarily need to consume all of her Moto.

Constraints

• 2 ≤ N ≤ 50
• 1 ≤ X ≤ 10^9
• 0 ≤ D ≤ 10^9
• 1 ≤ m_i ≤ 10^9 (1 ≤ i ≤ N)
• 1 ≤ p_i < i (2 ≤ i ≤ N)
• All values in input are integers.

Sample Input 1

3 100 1
15
10 1
20 1

Sample Output 1

7

She has 100 grams of Moto, can make three kinds of doughnuts, and the conditions that must hold are c_1 ≤ c_2 ≤ c_1 + 1 and c_1 ≤ c_3 ≤ c_1 + 1. It is optimal to make two Doughnuts 1, three Doughnuts 2 and two Doughnuts 3.

Sample Input 2

3 100 10
15
10 1
20 1

Sample Output 2

10

The amount of Moto and the recipes of the doughnuts are not changed from Sample Input 1, but the last conditions are relaxed. In this case, it is optimal to make just ten Doughnuts 2. As seen here, she does not necessarily need to make all kinds of doughnuts.

Sample Input 3

5 1000000000 1000000
123
159 1
111 1
135 3
147 3

Sample Output 3

7496296