Sweet Alchemy

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.

Input

Input is given from Standard Input in the following format:

N X D m_1 m_2 p_2 : m_N p_N

Output

Print the maximum number of doughnuts that can be made under the condition.

Examples

Input

3 100 1 15 10 1 20 1

Output

7

Input

3 100 10 15 10 1 20 1

Output

10

Input

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

Output

7496296

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N X D m_1 m_2 p_2 : m_N p_N

outputFormat

Output

Print the maximum number of doughnuts that can be made under the condition.

Examples

Input

3 100 1 15 10 1 20 1

Output

7

Input

3 100 10 15 10 1 20 1

Output

10

Input

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

Output

7496296

样例

3 100 10
15
10 1
20 1

10