Dreamy Graph Traversal

In this problem, you are given a tree consisting of n nodes and n-1 edges. In addition, there are m special nodes, each of which contains an anime character. Each character is associated with two parameters: \( pos_i \) (the node where the character is located) and \( val_i \) (the amount of joy obtained by chatting with that character). Chatting with any character does not consume time.

Every time zrz_orz dreams, he starts at node 1 and has a total of \( T \) time units. During his dream, he can traverse the tree along its edges. Note that each edge takes 1 unit of time to traverse. Most importantly, after finishing his dream he must return to node 1; otherwise, he will be lost in his dream.

Your task is to determine the maximum joy that can be obtained in one dream. The dream’s structure (tree and rewards) remains unchanged between dreams.

Note:

• The journey always starts at node 1.
• You may collect the joy value from a node if (and only if) that node contains an anime character. Each anime character can be chatted with at most once.
• Moving along an edge costs 1 unit of time, and chatting does not consume any time.
• You must plan a route that starts and ends at node 1 within a total time of \( T \) units.

Hint: Since the graph is a tree, there is a unique path between any pair of nodes. You might want to use a tree DP (dynamic programming) approach, where for each node, you compute an array \( dp[u][t] \) representing the maximum joy you can gain from the subtree of \( u \) if you start at \( u \) and return to \( u \) using \( t \) time units. Then, combine the DP from children subtrees using a knapSack-like merging process. Remember that to explore a child \( v \) from node \( u \), you must spend 2 extra time units (1 going from \( u \) to \( v \) and 1 returning from \( v \) to \( u \)).

inputFormat

The first line contains three integers \( n \), \( m \) and \( T \) — the number of nodes, the number of nodes with an anime character, and the total time available, respectively.

Then follow \( n-1 \) lines, each containing two integers \( u \) and \( v \), representing an undirected edge between nodes \( u \) and \( v \) (the tree edges).

Then follow \( m \) lines, each containing two integers \( pos_i \) and \( val_i \), meaning that there is an anime character at node \( pos_i \) with a joy value of \( val_i \).

It is guaranteed that the given graph is a tree. Node 1 is the starting (and ending) point of the journey.

outputFormat

Output a single integer, the maximum total joy that can be obtained by a route starting and ending at node 1 within \( T \) time units.

sample

3 2 4
1 2
2 3
1 10
3 5

15