To celebrate the start of the school year, your school has planted a cherry tree in the front yard. However, this is no ordinary cherry tree. This cherry tree has cherry patches, each with a specific number of cherries. It also has branches, each with a specific weight, connecting the patches to one another.

Yui is a big fan of cherry trees, but unfortunately does not have one of her own. She decides to make a single cut to the tree and take that part back home. She will only take home a portion that has at least cherries and a total branch weight which is at most .

Since patch is always connected to the trunk of the tree, she will never take home a portion that has patch (she isn't crazy enough to cut down the entire tree).

Since Yui isn't taking computer science this year, help her by writing a program to determine where to cut the tree!

#### Input Specification

The first line contains three space separated integers, , and , representing the number of patches on the tree, the number of cherries Yui wants, and the maximum weight she will take home.

The next line contains space separated integers , representing the number of cherries on the patch.

The next lines each contain three integers , and , representing the two patches that the branch connects as well as its weight.

#### Output Specification

Output one integer, indicating the number of possible unique cuts that Yui can make to fulfill her requirements.

#### Sample Input

```
8 5 15
1 5 9 4 3 4 8 2
1 2 3
1 3 2
2 4 5
2 5 4
3 6 6
3 7 9
3 8 1
```

#### Sample Output

`2`

#### Explanation for Sample Input

Shown below is a visualization of the tree in the sample input:

The larger number on each patch represents the number of cherries on that patch.

In this case, the branch connecting patches and can be cut to obtain a portion with cherries and a weight of . The branch connecting patches and can also be cut for cherries and a weight of .

## Comments

it's a good thing to know that nodes will always be the child of a node with a smaller number

this is actually helpful ngl (should be in the problem statement)

can someone send help pls i AC'ed a few cases but then i got the rest wrong pls help Edit: NVM i made some stupid mistake

Can you look my code? Maybe I didn't understand the problem right, which is common. notepad.pw/pequena_sereia

Help please?Can someone explain what I'm doing wrong?

Is it guaranteed that the farther away the patch is from patch 1, the larger the patch index?

Got everything correct until batch 2 case 6 and batch 3 case 6, what could I be missing, code works for sample input and all of batch one.

make sure your program works for certain edge cases (look at constraints)

Why am I getting invalid return?

Python has a relatively small recursion limit, try

Great, thanks!

For Python 3.x, use this

NVM got it. Apparently when you cut, the weight of the cut one is included and that was screwing me over.

Reading the explanation always helps!