#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
using i64 = int64_t;
using pii = pair<i64, i64>;
#define rep(i, n) for (i64 i = 0; i < (i64) n; i++)
#define per(i, n) for (i64 i = n - 1; i >= 0; i--)
#define REP(i, a, b) for (i64 i = a; i < (i64) b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#ifdef LOCAL
#define dbg(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug(__VA_ARGS__)
#else
#define dbg(...)
#endif
template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec) {
    for (auto& x : vec) { os << x << ' '; } return os;
}
template <typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& mat) {
    os << endl; for (auto& vec : mat) { os << vec << endl; } return os;
}
template <typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& pa) {
    os << '(' << pa.first << ',' << pa.second << ')'; return os;
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail> void debug(Head H, Tail... T) {
    cerr << " " << H; debug(T...);
}
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1 << 30) - 1;
const i64 LINF = (1LL << 62) - 1;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> G(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<int> dp(n), dp2(n);

    auto dfs = [&](auto self, int& t, int v = 0, int p = -1) -> int {
        int ret = 0;

        for (int& u : G[v]) {
            if (u == p) continue;
            ret += self(self, t, u, v);
            chmax(dp[v], dp[u] + 1);
            chmin(dp2[v], dp2[u] + 1);
        }
        
        if (dp[v] + dp2[v] <= t) dp[v] = -INF;

        if (dp[v] == t) {
            ret++;
            dp[v] = -INF;
            dp2[v] = 0;
        } else if (p == -1 && dp[v] >= 0) {
            ret++;
        }
        
        return ret;
    };

    auto check = [&](int t) -> bool {
        fill(all(dp), 0);
        fill(all(dp2), INF);
        int cnt = dfs(dfs, t);
        return cnt <= k;
    };

    int ok = n - 1, ng = -1;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

int dp[101][101][101];

void relax(int& val, int nval)
{
    if (val == -1)
        val = nval;
    val = max(val, nval);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    LL x;
    cin >> n >> x;
    VI a(n);
    FOR(i, 0, n)
    {
        cin >> a[i];
    }
    LL ans = x - *max_element(ALL(a));
    FOR(k, 2, n + 1)
    {
        FILL(dp, -1);
        dp[0][0][0] = 0;
        FOR(i, 0, n)
        {
            FOR(rem, 0, k)
            {
                FOR(cnt, 0, k + 1)
                {
                    if (dp[i][rem][cnt] == -1)
                        continue;
                    relax(dp[i + 1][rem][cnt], dp[i][rem][cnt]);
                    relax(dp[i + 1][(rem + a[i]) % k][cnt + 1], dp[i][rem][cnt] + a[i]);
                }
            }
        }
        LL sum = dp[n][x % k][k];
        if (sum != -1)
        {
            assert((x - sum) % k == 0);
            ans = min(ans, (x - sum) / k);
        }
    }
    cout << ans << '\n';
    return 0;
}