설명하기 어려운 문제

$N$개의 정점과 $N-1$개의 간선으로 이루어진 트리가 주어진다. 1번 정점은 트리의 루트이다. 각 정점 $i$에는 양의 정수 $A_i, B_i, C_i$가 주어지며, $C_1 = 10^9$이다. 또한 1이 아닌 모든 정점 $x$에 대해 $B_{parent(x)} \le B_x$이다. 여기서 $parent(x)$는 $x$의 부모 정점이다.

숫자가 적힌 트리를 보면 자연스럽게 질의를 하고 싶어진다. 각 질의는 정점 $V$와 정수 $T$로 주어진다. 1번 정점과 $V$를 잇는 최단 경로 위에 있고 $C_i \geq T$를 만족하는 모든 정점 $i$에 대해, $A_i + B_i \times T$의 최솟값을 구한다. $T \le 10^9$이면 최솟값이 항상 존재한다.

첫 줄에 두 정수 $N$과 $Q$가 주어진다 ($1 \le N \le 80000$, $1 \le Q \le 160000$).

다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어진다 ($1 \le A_i \le 10^9$).

다음 줄에 $N$개의 정수 $B_1, B_2, \cdots, B_N$이 주어진다 ($1 \le B_i \le 10^9$).

다음 줄에 $N$개의 정수 $C_1, C_2, \cdots, C_N$이 주어진다 ($1 \le C_i \le 10^9$).

이어지는 $N-1$개의 줄에는 간선의 양 끝점 $X$와 $Y$가 주어진다 ($1 \le X, Y \le N$).

이어지는 $Q$개의 줄에는 질의의 인자인 정점 $V$와 정수 $T$가 주어진다 ($1 \le V \le N$, $0 \le T \le 10^9$).

$C_1 = 10^9$이고, 1이 아닌 모든 정점 $x$에 대해 $B_{parent(x)} \le B_x$임이 보장된다.

$Q$개의 줄을 출력한다. 각 줄에는 해당 질의의 답인 최솟값을 정수 하나로 출력한다.