Minimizing Children's Dissatisfaction Under Teacher Constraints

You are given a tree with \(n\) rooms (nodes) connected by \(n-1\) bidirectional roads (edges). The \(i\)-th road connects room \(u_i\) and room \(v_i\). When all roads are open the tree is connected. Each room \(i\) has an associated value \(h_i\).

You are allowed to close some of the roads. Once some roads are closed, the tree splits into a forest (i.e. several connected components). In each connected component, the children's dissatisfaction is defined as the difference between the maximum and minimum \(h\) values in that component. The children’s total dissatisfaction is the maximum such difference over all connected components.

There are also \(m\) teachers. The \(i\)-th teacher will walk along the unique path from room \(x_i\) to room \(y_i\) (this path is determined using the original tree when all roads are open). If a teacher passes by a road that is closed, that teacher becomes dissatisfied; the teacher’s dissatisfaction is defined as the number of closed roads encountered on the path. The teachers' total dissatisfaction is the sum of the dissatisfaction values of all teachers.

Ysuperman can tolerate at most \(k\) total teacher dissatisfaction. Your task is to choose a set of roads to close so that the teachers' total dissatisfaction does not exceed \(k\) and the children’s total dissatisfaction is minimized. Output this minimum possible children’s total dissatisfaction.

Note: Any formula in the statement is written in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) \( (1 \leq n \leq 15,\ 1 \leq m, k \leq 10^9)\) — the number of rooms, the number of teachers, and the maximum total teacher dissatisfaction allowed.

The second line contains \(n\) integers \(h_1, h_2, \ldots, h_n\) representing the difference values of the rooms.

The next \(n-1\) lines each contain two integers \(u_i\) and \(v_i\) \( (1 \leq u_i, v_i \leq n)\) representing a bidirectional road between rooms \(u_i\) and \(v_i\). It is guaranteed that if all roads are open, the graph is connected.

The next \(m\) lines each contain two integers \(x_i\) and \(y_i\) \( (1 \leq x_i, y_i \leq n)\) representing the start and end room of the teacher's path.

outputFormat

Output a single integer: the minimum possible children’s total dissatisfaction (i.e. the minimum possible maximum difference \(\max_{C}(\max_{v \in C} h_v - \min_{v \in C} h_v)\) among all connected components) such that the teachers' total dissatisfaction does not exceed \(k\).

sample

3 1 0
1 3 2
1 2
2 3
1 3

2