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;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 50 + 11;
int n, m;
bool painted[NMAX][NMAX];
vector<ii> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
inline bool valid(int r, int c)
{
    return 0 <= r and r < n and 0 <= c and c < m;
}
vector<ii> get_neighbors(int r, int c)
{
    vector<ii> ans;
    for (auto [dr, dc] : directions)
        if (valid(r + dr, c + dc) and painted[r + dr][c + dc])
            ans.emplace_back(r + dr, c + dc);
    return ans;
}
bool bfs(int r, int c, vector<ii> targets)
{
    vector<vector<bool>> visited(n, vector<bool>(m, 0));
    queue<ii> frontier;
    visited[r][c] = true;
    frontier.emplace(r, c);
    while (not frontier.empty())
    {
        auto [r, c] = frontier.front();
        frontier.pop();
        if (auto it = find(targets.begin(), targets.end(), make_pair(r, c)); it != targets.end())
        {
            targets.erase(it);
            if ((int)targets.size() == 0)
            {
                return true;
            }
        }
        for (auto [rr, cc] : get_neighbors(r, c))
        {
            if (not visited[rr][cc])
            {
                frontier.emplace(rr, cc);
                visited[rr][cc] = true;
            }
        }
    }
    return false;
}
int main(void)
{
    cin >> n >> m;
    int asz = 0;
    char ch;
    for (int r = 0; r < n; ++r)
        for (int c = 0; c < m; ++c)
            cin >> ch, painted[r][c] = (ch == '#'), asz += painted[r][c];
    if (asz <= 2)
        cout << -1 << endl;
    else
    {
        for (int r = 0; r < n; ++r)
        {
            for (int c = 0; c < m; ++c)
            {
                if (not painted[r][c])
                    continue;
                auto neighbors = get_neighbors(r, c);
                auto [rr, cc] = neighbors.back();
                neighbors.pop_back();
                painted[r][c] = false;
                if ((int)neighbors.size() == 0 or not bfs(rr, cc, neighbors))
                {
                    cout << 1 << endl;
                    return 0;
                }
                painted[r][c] = true;
            }
        }
        cout << 2 << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int const LMAX = 18;
int n, val[NMAX], tin[NMAX], tout[NMAX], up[NMAX][LMAX + 1], ssize[NMAX],
    depth[NMAX], timer;
ii edges[NMAX];
vi g[NMAX];
void precompute_lca(int u, int p)
{
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i <= LMAX; ++i)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : g[u])
        if (v != p)
            precompute_lca(v, u);
    tout[u] = ++timer;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = LMAX; i >= 0; --i)
    {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
void precompute_sz(int u, int p = 0)
{
    ssize[u] = val[u];
    depth[u] = depth[p] + 1;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        precompute_sz(v, u);
        ssize[u] += ssize[v];
    }
}
int main(void)
{
    int k, u, v, root = 1;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }
    precompute_lca(root, root);
    cin >> k;
    while (k--)
    {
        cin >> u >> v;
        val[lca(u, v)] -= 2;
        val[u] += 1;
        val[v] += 1;
    }
    precompute_sz(root);
    for (int i = 0; i < n - 1; ++i)
    {
        auto [u, v] = edges[i];
        if (depth[u] < depth[v])
            swap(u, v);
        cout << ssize[u] << " ";
    }
    cout << endl;
    return 0;
}

using namespace std;
int n;
int v[3];
int mem[4010];
bool vis[4010];
int dp(int remainder)
{
    if (remainder == 0)
        return 0;
    else if (remainder < 0)
        return INT_MIN;
    if (vis[remainder])
        return mem[remainder];
    int ans = INT_MIN;
    for (int i = 0; i < 3; ++i)
    {
        ans = max(ans, 1 + dp(remainder - v[i]));
    }
    vis[remainder] = true;
    mem[remainder] = ans;
    return ans;
}
int main(void)
{
    cin >> n >> v[0] >> v[1] >> v[2];
    cout << dp(n) << endl;
    return 0;
}

using namespace std;
bool solve(int a, int b)
{
    if (a < b)
        swap(a, b);
    int diff = a - b;
    if (b < diff)
        return false;
    a -= 2 * diff;
    b -= diff;
    return (a % 3 == 0);
}
int main(void)
{
    int t, a, b;
    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        cout << (solve(a, b) ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
vi prefix_function(string s)
{
    int n = s.size();
    vi pi(n, 0);
    for (int i = 1; i < n; ++i)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            ++j;
        pi[i] = j;
    }
    return pi;
}
int solve(string s, string p)
{
    int m = p.size();
    auto pi = prefix_function(p + '#' + s);
    return count_if(pi.begin(), pi.end(), [m](int x) { return x == m; });
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    string s, p;
    cin >> s >> p;
    cout << solve(s, p) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 2e5 + 11;
const int PTWO = 32;
int _succ[NMAX][PTWO];
int succ(int x, int k, int i = 0)
{
    if (k == 0)
        return x;
    if (k == 1)
        return _succ[x][i];
    int rem = k % 2;
    if (rem == 1)
        return _succ[succ(x, k / 2, i + 1)][i];
    else
        return succ(x, k / 2, i + 1);
}
int main(void)
{
    int n, q, x, k;
    cin >> n >> q;
    for (int u = 1; u <= n; ++u)
        cin >> _succ[u][0];
    for (int p = 1; p < PTWO; ++p)
    {
        for (int u = 1; u <= n; ++u)
        {
            _succ[u][p] = _succ[_succ[u][p - 1]][p - 1];
        }
    }
    while (q--)
    {
        cin >> x >> k;
        cout << succ(x, k) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
template <long long M, typename T = long long>
class NumMod
{
    static_assert(std::is_integral<T>::value, "Integral required.");
    using NM = NumMod<M, T>;
    T x;
  public:
    static const ll MOD = M;
    NumMod(T x) : x(x) {}
    NumMod() : x(0) {}
    NumMod(NM const &y) : x(y.v()) {}
    explicit operator T() const { return x; }
    T v(void) const { return (this->x + M) % M; }
    NM & operator=(NM const &y)
    {
        this->x = y.v();
        return *this;
    }
    NM &operator=(T const &y) { return this->operator=(NM(y)); }
    NM &operator+=(NM const &y) { return this->operator=(operator+(y)); }
    NM &operator-=(NM const &y) { return this->operator=(operator-(y)); }
    NM &operator*=(NM const &y) { return this->operator=(operator*(y)); }
    NM operator+(NM const &y) const { return (v() + y.v()) % M; }
    NM operator+(T const &y) const { return this->operator+(NM(y)); }
    NM operator-(NM const &y) const { return (v() - y.v()) % M; }
    NM operator-(T const &y) const { return this->operator-(NM(y)); }
    NM operator*(NM const &y) const { return (v() * y.v()) % M; }
    NM operator*(T const &y) const { return this->operator*(NM(y)); }
};
ll const MOD = 1e9 + 7;
using NM = NumMod<MOD, ll>;
ll solve(int n, int m, vi a)
{
    vector<vector<NM>> dp(n + 1, vector<NM>(m + 2, 0));
    if (a[1] == 0)
        for (int x = 1; x <= m; ++x)
            dp[1][x] = 1;
    else
        dp[1][a[1]] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] == 0)
            for (int x = 1; x <= m; ++x)
                dp[i][x] = dp[i - 1][x - 1] + dp[i - 1][x] + dp[i - 1][x + 1];
        else
        {
            dp[i][a[i]] =
                dp[i - 1][a[i] - 1] + dp[i - 1][a[i]] + dp[i - 1][a[i] + 1];
        }
    }
    return ll(accumulate(dp[n].begin(), dp[n].end(), NM(0)));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi a(n + 1, 0);
    read_n(next(a.begin()), n);
    cout << solve(n, m, a) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using si = set<int>;
int main(void)
{
    int n;
    vi x;
    si sums;
    cin >> n;
    x.resize(n);
    for (auto &xi : x)
        cin >> xi;
    for (auto xi : x)
    {
        si temp;
        for (auto sum : sums)
            temp.insert(sum + xi);
        sums.insert(xi);
        sums.insert(temp.begin(), temp.end());
    }
    cout << sums.size() << endl;
    for (auto sum : sums)
    {
        cout << sum << " ";
    }
    cout << endl;
    return 0;
}