using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int n;
ll val[NMAX];
vi g[NMAX];
array<ll, 2> dfs(int u, int p)
{
    array<ll, 2> ans = {0, 0};
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        auto cur = dfs(v, u);
        ans = {max(ans[0], cur[0]), max(ans[1], cur[1])};
    }
    val[u] += ans[0] - ans[1];
    ans[val[u] >= 0] += abs(val[u]);
    val[u] = 0;
    return ans;
}
int main(void)
{
    int u, v;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        cin >> val[i];
    auto ans = dfs(1, -1);
    cout << accumulate(ans.begin(), ans.end(), 0LL) << endl;
    return 0;
}

using namespace std;
int digit_at(int number, int pos) {
  return number / (1000 / (int)pow(10, pos)) % 10;
}
bool is_valid(int y1, int y2) {
  set<int> digits;
  for (int i = 0; i < 4; ++i) {
    int n = digit_at(y2, i);
    if (digits.find(n) != digits.end())
      return false;
    digits.insert(n);
  }
  return true;
}
int get_next(int year) {
  int y = year;
  while (not is_valid(year, ++y))
    ;
  return y;
}
int main(void) {
  int year;
  cin >> year;
  cout << get_next(year) << endl;
  return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, ans = 0;
    cin >> n;
    vi h(n), a(n);
    for (int i = 0; i < n; ++i)
        cin >> h[i] >> a[i];
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (i == j)
                continue;
            ans += (h[i] == a[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, last, ans = 0;
    string s;
    cin >> n >> s;
    last = 0;
    for (auto c : s)
    {
        if (c == last)
            ++ans;
        last = c;
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int cell, ans = 0;
    for (int i = 1; i <= 5; ++i)
    {
        for (int j = 1; j <= 5; ++j)
        {
            cin >> cell;
            if (cell)
                ans = abs(3 - i) + abs(3 - j);
        }
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
ii const EMPTY = {-1, -1};
ii solve(int n, vi &a)
{
    if (n <= 2)
        return EMPTY;
    if (all_of(a.begin(), a.end(), [&a](int x) { return x == a[0]; }))
        return EMPTY;
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (a[i] != a[j])
            {
                swap(a[i], a[j]);
                if (not is_sorted(a.begin(), a.end()) and
                    not is_sorted(a.begin(), a.end(), greater<int>()))
                    return {i + 1, j + 1};
                swap(a[i], a[j]);
            }
        }
    }
    return EMPTY;
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int n;
    vi a;
    cin >> n;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai;
    if (auto ans = solve(n, a); ans != EMPTY)
        cout << ans.first << " " << ans.second << endl;
    else
        cout << "-1" << endl;
    return 0;
}

using namespace std;
int main(void)
{
    string s;
    vector<bool> alph(26, false);
    string msg[2] = {"CHAT WITH HER!", "IGNORE HIM!"};
    cin >> s;
    for (auto c : s)
        alph[c - 'a'] = true;
    bool ans = accumulate(alph.begin(), alph.end(), 0) % 2;
    cout << msg[ans] << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, cnt, ans = 0;
    bool sure;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cnt = 0;
        for (int j = 0; j < 3; ++j)
        {
            cin >> sure;
            cnt += sure;
        }
        if (cnt >= 2)
            ++ans;
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
ll iceil(ll a, ll b) { return (a + b - 1) / b; }
ll solve(
    int n, int m, vll const &t, vll const &T, vll const &x, vll const &cost)
{
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ll safe_children_per_bus = min(max(T[i] - t[i], 0LL), (ll)m);
        ll one = cost[i] + x[i] * (safe_children_per_bus == m ? 0 : m);
        if (safe_children_per_bus == 0 or safe_children_per_bus == m)
        {
            ans += one;
            continue;
        }
        ll nbuses = iceil(m, safe_children_per_bus);
        ll spaced = nbuses * cost[i];
        ans += min(one, spaced);
    }
    return ans;
}
int main(void)
{
    int n, m;
    vll t, T, x, cost;
    cin >> n >> m;
    t.resize(n), T.resize(n), x.resize(n), cost.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> t[i] >> T[i] >> x[i] >> cost[i];
    cout << solve(n, m, t, T, x, cost) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, m;
    vi a, b;
    cin >> n;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai;
    cin >> m;
    b.resize(m);
    for (auto &bi : b)
        cin >> bi;
    reverse(b.begin(), b.end());
    multiset<int, greater<int>> ms;
    for (auto bi : b)
    {
        for (auto ai : a)
        {
            if (bi % ai == 0)
            {
                ms.insert(bi / ai);
            }
        }
    }
    cout << ms.count(*ms.begin()) << endl;
    return 0;
}