Задача . E. LuoTianyi и Картридж

LuoTianyi смотрит аниме Made in Abyss. Она считает, что создание Картриджа является очень интересным занятием. Чтобы более четко описать процесс создания Картриджа, она абстрагируется от исходной задачи и даёт вам следующую.

Вам дано дерево \(T\), состоящее из \(n\) вершин. Каждая вершина имеет значения \(a_i\) и \(b_i\), а каждое ребро имеет значения \(c_j\) и \(d_j\).

Теперь вам нужно построить дерево \(T'\) следующим образом:

• Сначала выберите \(p\) вершин из \(T\) (\(p\) — число, выбранное вами самостоятельно) в качестве множества вершин \(S'\) в \(T'\);
• Затем последовательно выберите \(p-1\) ребро из \(T\) по одному (нельзя выбирать одно ребро более одного раза);
• Пусть вы выбрали \(j\)-е ребро, и оно соединяет вершины \(x_j\) и \(y_j\) и имеет значения \((c_j,d_j)\). Тогда вы можете выбрать две вершины \(u\) и \(v\) в \(S'\), для которых ребро \((x_j,y_j)\) лежит на простом пути из \(u\) в \(v\) в \(T\), и соединить \(u\) и \(v\) в \(T'\) ребром со значениями \((c_j,d_j)\) (\(u\) и \(v\) не должны содержаться в одной компоненте связности ранее в \(T'\)).

Дерево с тремя вершинами, \(\min(A,C)=1,B+D=7\), стоимость равна \(7\).

Выбрали вершины \(2\) и \(3\) как \(S'\), использовали ребро \((1,2)\) с \(c_j = 2\) и \(d_j = 1\), чтобы соединить эти вершины, теперь \(\min(A,C)=2,B+D=4\), стоимость равна \(8\).

Пусть \(A\) — минимум из значений \(a_i\) в \(T'\), и \(C\) — минимум из значений \(c_i\) в \(T'\). Пусть \(B\) — сумма значений \(b_i\) в \(T'\), и \(D\) — сумма значений \(d_i\) в \(T'\). Определим \(\min(A, C) \cdot (B + D)\) как стоимость \(T'\). Вам нужно найти максимально возможную стоимость \(T'\).