/**
* APIO 2016 - Fireworks
* Solution using Slope Trick and Leftist Heaps
* Time Complexity: O((N+M) log (N+M))
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Leftist Heap Node
struct Node {
long long val;
int dist; // Null Path Length for Leftist property
Node *l, *r;
Node(long long v) : val(v), dist(0), l(nullptr), r(nullptr) {}
};
// Merge two Leftist Heaps (Max Heap)
Node* merge(Node* a, Node* b) {
if (!a) return b;
if (!b) return a;
// Max Heap property: larger value at root
if (a->val < b->val) swap(a, b);
a->r = merge(a->r, b);
// Leftist property: dist of left child >= dist of right child
if (!a->l || a->l->dist < a->r->dist) swap(a->l, a->r);
a->dist = a->r ? a->r->dist + 1 : 0;
return a;
}
// Pop root and return new root
Node* pop(Node* root) {
if (!root) return nullptr;
Node* res = merge(root->l, root->r);
delete root; // Clean up memory
return res;
}
const int MAXN = 300005;
vector<int> adj[MAXN];
long long edge_weight[MAXN];
Node* heaps[MAXN];
long long total_edge_sum = 0;
void dfs(int u) {
// Process all children
for (int v : adj[u]) {
dfs(v);
heaps[u] = merge(heaps[u], heaps[v]);
}
if (u != 1) { // If not root
if (adj[u].empty()) {
// Leaf Node Logic
// Function is |x - w|, slopes change at w and w
long long w = edge_weight[u];
heaps[u] = merge(heaps[u], new Node(w));
heaps[u] = merge(heaps[u], new Node(w));
} else {
// Internal Node Logic
int deg = adj[u].size();
// Pop 'deg - 1' largest breakpoints to flatten slope > 1 to 1
while (deg > 1) {
heaps[u] = pop(heaps[u]);
deg--;
}
// Extract the optimal interval [L, R]
long long R = heaps[u]->val; heaps[u] = pop(heaps[u]);
long long L = heaps[u]->val; heaps[u] = pop(heaps[u]);
// Shift by edge weight and push back
// The cost function is extended by w
heaps[u] = merge(heaps[u], new Node(R + edge_weight[u]));
heaps[u] = merge(heaps[u], new Node(L + edge_weight[u]));
}
} else {
// Root Logic
int deg = adj[u].size();
// We want the minimum value, which occurs when slope is 0.
// The heap currently ends with max slope 'deg'.
// We pop 'deg' times to remove all positive slope parts.
while (deg > 0) {
heaps[u] = pop(heaps[u]);
deg--;
}
// The minimum cost is: (Sum of all weights) - (Sum of remaining breakpoints)
// This formula derives from integrating the negative slopes.
while (heaps[u]) {
total_edge_sum -= heaps[u]->val;
heaps[u] = pop(heaps[u]);
}
}
}
int main() {
// Optimize I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
if (!(cin >> N >> M)) return 0;
// Input format: Line i (for i=2...N+M) contains Parent and Weight
for (int i = 2; i <= N + M; i++) {
int p;
long long w;
cin >> p >> w;
adj[p].push_back(i);
edge_weight[i] = w;
total_edge_sum += w;
}
dfs(1);
cout << total_edge_sum << endl;
return 0;
}
