Best Triangular Hamilton Path

Given a map of n islands and m bridges connecting them, each island i is associated with a positive integer value \(V_i\). A Hamilton path is a path along bridges that visits each island exactly once. The value of a Hamilton path \(C_1C_2\dots C_n\) is defined as the sum of three parts:

• Vertex Sum: \(\sum_{i=1}^{n}V_{C_i}\).
• Edge Sum: For every consecutive islands in the path, add \(V_{C_i}\times V_{C_{i+1}}\).
• Triangle Bonus: For every three consecutive islands \(C_i, C_{i+1}, C_{i+2}\) that form a triangle (i.e. there is a direct bridge between \(C_i\) and \(C_{i+2}\)), add \(V_{C_i}\times V_{C_{i+1}}\times V_{C_{i+2}}\).

Your task is to compute two values: the maximum possible value of a Hamilton path and the number of Hamilton paths that achieve this maximum value. It is guaranteed that the best path may contain many triangles. Note that two paths which are reversals of each other are considered distinct if they are obtained in different orders.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of islands and the number of bridges, respectively. \(n\) is small (e.g. \(n \leq 16\)).

The second line contains \(n\) positive integers: \(V_1, V_2, \dots, V_n\), where \(V_i\) denotes the value of island i.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating that there is a bridge connecting island \(u\) and island \(v\). It is guaranteed that there is at most one bridge between any two islands and the bridges are bidirectional.

outputFormat

Output two space‐separated integers: the maximum value of a triangular Hamilton path, and the number of such paths achieving this maximum.

sample

3 3
1 2 3
1 2
2 3
1 3

21 2