## Back to School '16: Cherry Tree

View as PDFTo 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

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

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