Given a rooted tree $T$ with $n$ nodes, labeled $1$ to $n$, where $1$ is the root. Each node has two integer weights $a_i$ and $b_i$.

A set of nodes $S$ is called "good" if and only if it satisfies the following condition: $\forall u, v \in S$ such that $u$ is an ancestor of $v$, there exists $x \notin S$ and $y \in S$ such that: $x$ is on the path from $u$ to $v$; * $b_y \leq b_x$.

Given $q$ queries, each providing positive integers $c, d$, find a good set $S$ that maximizes $c \times (\sum_{u \in S} a_u) + d \times (\min_{u \in S} b_u)$. You only need to output this maximum value. When $S$ is empty, we define $\min_{u \in S} b_u = 0$.

Input

The input is read from standard input. The first line contains two integers $n$ and $q$, describing the number of nodes in the tree and the number of queries. The next $n - 1$ lines each contain two integers $u, v$, describing an edge of the tree. The next $n$ lines each contain two integers $a_i, b_i$, describing the weights of node $i$. The next $q$ lines each contain two integers $c, d$, describing a query.

Output

Output to standard output. For each query, output a single integer on a new line representing the answer.

Examples

Input 1

3 4
1 2
1 3
1 -2
-2 1
-5 2
1 1
1 3
3 1
1 10

Output 1

0
1
1
15

Note

The sets chosen for the four queries are $\emptyset, \{2\}, \{1\}, \{3\}$ respectively.

Constraints

For all test data: $1 \leq n, q \leq 3 \times 10^5$; $1 \leq u \neq v \leq n$, the given $n - 1$ edges are guaranteed to form a tree; $-10^4 \leq a_i \leq 10^4$, $-10^9 \leq b_i \leq 10^9$; $1 \leq c, d \leq 10^8$.

Subtasks