#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>
#include <cmath>
#include <iomanip>
#include <iterator>
#include <bitset>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <chrono>
#include <random>
#include <array>
#include <functional>
#include <random>
///1:54
using namespace std;
const int maxN = 300009;
int N, M, t[maxN], d[maxN], sz[maxN];
vector<int> v[maxN];
const bool DBG = 0;
namespace brute {
const int maxK = 100;
long long bruteDp[maxN][100];
int mod(int x) { return (x < 0 ? -x : x); }
void doBrute() {
for (int i = N; i >= 1; i--) {
if (v[i].empty()) {
for (int j = 0; j < maxK; j++)
bruteDp[i][j] = j;
} else {
for (int j = 0; j < maxK; j++) {
for (auto it: v[i]) {
long long best = 0;
for (int k = 0; k <= j; k++) {
long long curr = bruteDp[it][k] + mod((j - k) - d[it]);
if (curr < best || k == 0)
best = curr;
}
bruteDp[i][j] += best;
}
if (j > 0)
bruteDp[i][j] = min(bruteDp[i][j], bruteDp[i][j - 1] + 1);
}
}
}
long long ans = bruteDp[1][0];
for (int i = 1; i < maxK; i++)
ans = min(ans, bruteDp[1][i]);
printf("brute: %lld\n", ans);
}
};
void dfsSz(int nod) {
int pos = 0, heaviest = -1;
sz[nod] = 1;
for (auto it : v[nod]) {
dfsSz(it);
sz[nod] += sz[it];
if (heaviest == -1 || sz[it] > sz[v[nod][heaviest]])
heaviest = pos;
pos ++;
}
if (heaviest > 0)
swap(v[nod][heaviest], v[nod][0]);
}
struct dpFunction {
multiset<long long> S;
long long platformLength = 0, smallest = 0;
long long platformStart() {
if (S.empty()) return 0;
return *S.rbegin();
}
void addD(int d) {
if (S.empty()) {
S.insert(d);
return ;
}
auto it = S.end(); it --;
S.insert(*it + d);
S.erase(it);
}
void operator += (const dpFunction& other) {
for (auto it : other.S)
S.insert(it);
smallest += other.smallest;
}
void print() {
printf("{");
for (auto it : S)
printf("%lld,", it);
printf("\b} min=%lld, platform=%lld", smallest, platformLength);
}
void printVals(int nodeToCompare = -1) {
if (S.empty()) {
printf("flat at [%lld, %lld]\n", platformStart(), platformStart() + platformLength);
return ;
}
vector<long long> f(max<int>(platformStart() + platformLength + 10, brute::maxK), 0LL);
auto it = S.end(); it --;
int slope = 0;
long long curr = smallest;
for (int i=platformStart() + platformLength; i>=0; i--) {
while (it != S.begin() && *it >= i)
slope ++, it --;
f[i] = curr, curr += slope + (*it >= i);
}
curr = smallest;
for (int i=platformStart() + platformLength + 1; i<f.size(); i++)
curr ++, f[i] = curr;
if (nodeToCompare != -1) {
bool areSame = 1;
for (int i = 0; i < f.size(); i++)
areSame &= (f[i] == brute::bruteDp[nodeToCompare][i]);
if (!areSame) {
printf("WA %d:\n", nodeToCompare);
for (int i = 0; i < f.size(); i++)
printf("%2d ", i);
printf("\n");
for (auto it: f)
printf("%2lld ", it);
printf("\ninstead of \n");
for (int i = 0; i < f.size(); i++)
printf("%2lld ", brute::bruteDp[nodeToCompare][i]);
exit(0);
}
} else {
for (auto it : f)
printf("%2d ", it);
printf("\n");
}
}
}dp[20];
void solve(int nod, int lev) {
if (v[nod].empty()) {
dp[lev] = dpFunction();
return ;
}
vector<long long> rightEnds;
for (auto it : v[nod]) {
if (it != v[nod][0]) {
dp[lev + 1] = dpFunction();
solve(it, lev + 1);
dp[lev + 1].addD(d[it]);
dp[lev] += dp[lev + 1];
rightEnds.push_back(dp[lev + 1].platformStart() + dp[lev + 1].platformLength);
} else {
solve(it, lev);
dp[lev].addD(d[it]);
rightEnds.push_back(dp[lev].platformStart() + dp[lev].platformLength);
}
}
if (DBG) {
printf("rightEnds:[");
for (auto it: rightEnds)
printf("%lld ", it);
printf("\b]\n");
printf("before rightEnds: "), dp[lev].print(), printf("\n");
dp[lev].printVals();
}
sort(rightEnds.rbegin(), rightEnds.rend());
for (auto x : rightEnds) {
dp[lev].S.insert(x);
//dp[lev].print(), printf("following %d\n", x);
auto it2 = dp[lev].S.end(); it2 --;
auto it = it2; it --;
dp[lev].platformLength = *it2 - *it;
dp[lev].smallest += *it2 - x;
dp[lev].S.erase(it2);
}
if (DBG) {
printf("node %d: "), dp[lev].print(), printf("\n");
dp[lev].printVals(nod);
}
}
int main() {
//freopen("../input", "r", stdin);
//freopen("../output", "w", stdout);
scanf("%d %d", &N, &M), N += M;
for (int i=2; i<=N; i++) {
scanf("%d %d", &t[i], &d[i]);
v[t[i]].push_back(i);
}
if (DBG) brute::doBrute();
dfsSz(1);
solve(1, 0);
printf("%lld\n", dp[0].smallest);
return 0;
}
/*const int seed = time (0);
mt19937 gen (seed);
long long getRand(long long a, long long b) {return uniform_int_distribution < long long > (a, b) (gen);}*/
