华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程

目录

题目

思路

Code

题目

题目内容：

小华平时要带着 C 名 AI Agent 一起赶一个项目。项目规模按代码行来计，一共是 G 行 Loc。他打算把这些行数拆给不同的 AI Agent，并让自己用来交代任务的时间尽量短。

AI Agent 听得懂自然语言。小华把需求讲完，再交由它去完成。

一名 AI Agent 好不好用，由下面三个量决定：

1. **委托效率**：小华对着这名 AI Agent 讲需求、对齐方案时，它每分钟能消化并记住的代码行数，记作 et 行每分钟。

2. **最低消费**：模型调用的费用由小华自己付。为了吃到便宜套餐，一旦启用这名 AI Agent，购买时长不能短于 ut 分钟。

3. **最高消费**：各家模型单价不同，小华给每名 AI Agent 卡了花费上限，购买时长不能长于 vt 分钟。

再补三条：

1. 小华在意的是自己何时能把任务全部交代完、从而空出手，并不在意项目最终哪一天收尾。所以各名 AI Agent 谁先谁后都无所谓。

2. 交互效率保持不变，多出来的额度可以闲置。已购买的套餐能覆盖的代码行数达到 G 行即可。

3. 同一时刻小华只能跟一名 AI Agent 交谈，任务得一个一个交代。

请给出购买方案，使这些套餐覆盖的行数不少于 G，并且购买分钟数之和最小。输出这个最小的分钟数。

## 输入描述

第一行是两个整数 C 和 G。C 表示 AI Agent 有几名，G 表示项目一共有多少行 Loc。

其后 C 行，每一行三个整数 et、ut、vt。这三个数按顺序对应该名 AI Agent 的委托效率、它的最低消费，以及它的最高消费。

数据范围：

- C ≤ 50

- G < 1000000000

- 1000 ≤ et < 10000

- 1 ≤ ut < 100000

- 1 ≤ vt < 100000

## 输出描述

输出一个整数，表示覆盖全部行数所需购买分钟数的最小值。若把每名 AI Agent 都买到最高消费仍不够，则输出 -1。

样例1

输入：

2 20000
9000 3 8
4000 2 6

输出：

3

说明：效率 9000 的那名至少买 3 分钟，得到 27000 行，已经盖过 20000 行，用时 3 分钟。另一名要买满 5 分钟才够 20000 行。因此最少是 3 分钟。

思路

整体思路：这是"最少买多少分钟才能凑够 G 行"的组合优化题。每名代理要么不买，要么买的分钟数落在 [u, v] 里；要在覆盖行数不少于 G 的前提下让总分钟数最少。把"总分钟数"看成背包容量、"覆盖行数"看成价值，就是一道按分钟数做阶段的背包 DP；再用滑动窗口最大值，把每个阶段的转移摊薄到每个分钟数只算一次。

1. 先做可行性和上界估计：若把每名代理都买到最高消费（效率 × 最高消费求和）仍盖不住 G，直接输出 -1。否则把代理按效率从高到低排，逐个"能买多少买多少"（至少买 u、最多买 v、够用就停），凑出一个可行方案，记它的总分钟数为 H。最优答案不会超过 H，所以 DP 只需要覆盖 0 到 H 这些分钟数，H 在本题数据范围内约是百万级。

2. 状态设计：dp[t] 表示"恰好花 t 分钟"时能覆盖的最大行数；凑不出恰好 t 分钟的状态用一个极小的哨兵值标记为不可达。初始化 dp[0] = 0，其余全部不可达。注意"恰好 t 分钟"和"至多 t 分钟"在这里等价可用：多买的分钟数只会增加覆盖，答案取的是第一个满足 dp[t] ≥ G 的 t，所以按"恰好"算不会漏掉最优解。

3. 逐个加入代理。设当前代理效率为 e、区间为 [u, v]。不买它时，新 dp[t] 沿用旧 dp[t]；买它 x 分钟（x 必须在 [u, v] 内）时，其余代理花 s = t - x 分钟，新覆盖 = 旧状态在 s 的最大覆盖 + e×x。也就是要在旧数组的下标区间 [t-v, t-u] 里找一个 s，使 old[s] + e×(t-s) 最大。

4. 把 old[s] + e×(t-s) 改写成 e×t + (old[s] - e×s)。对固定的 e 和 t，第二项只跟 s 有关，而且窗口 [t-v, t-u] 随 t 每次右移一格——这是标准的滑动窗口最大值：用单调双端队列维护"窗口内 old[s] - e×s 最大的 s"，队头永远是最划算的 s，均摊每个 s 只进队出队一次。窗口左端越过 0 时，用"在数组前面补哨兵"的技巧统一处理，不用分两类讨论。

5. 全部代理处理完后，从小到大扫 t，第一个满足 dp[t] ≥ G 的 t 就是答案；扫完都没有就输出 -1（前面已在可行性判断里兜住，这里只是双保险）。

复杂度：设 H 为贪心上界，每个代理的转移是 O(H)，总共 O(C×H) 时间、O(H) 空间。C ≤ 50、H 约百万级，乘起来约五千万次基本操作，在 C/C++/Java/Go 里轻松通过；Python 版本把滑窗最大值写成块内前缀/后缀最大值的分块法（窗口宽度恰好等于块长，每个位置只做常数次比较），配合逐元素 map 操作在 C 层完成，同样能在时限内跑完。关键坑点：u > v 的代理永远买不了，要先剔除；u 是"启用最低消费"，一旦买就至少 u 分钟，不能只买刚好够用的那几行；G ≤ 0 时一分钟都不用买，直接输出 0；"恰好 t 分钟"的不可达状态要与"覆盖为 0"区分，哨兵值必须远小于任何真实覆盖数，否则会被滑窗误当成合法状态；H 和覆盖数都能到几十亿，所有语言都要用 64 位整数。

Code

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 返回覆盖 G 行所需的最少购买分钟数，做不到返回 -1。
// agents 每项是 {效率 e, 最低消费 u, 最高消费 v}。
ll minMinutes(ll G, vector<array<ll, 3>>& agents) {
    if (G <= 0) return 0;              // 一行都不用覆盖，一分钟都不买

    vector<array<ll, 3>> items;
    ll total = 0;
    for (auto& a : agents) {
        ll e = a[0], u = a[1], v = a[2];
        if (u <= v) {                  // u > v 的代理买不了，剔除
            items.push_back({e, u, v});
            total += e * v;
        }
    }
    if (total < G) return -1;          // 全买到最高消费也盖不住，无解

    // 按效率从高到低贪心买一个可行方案，总分钟 H 作为 DP 上界
    sort(items.begin(), items.end(), [](const array<ll, 3>& a, const array<ll, 3>& b) {
        return a[0] > b[0];
    });
    ll remain = G, H = 0;
    for (auto& [e, u, v] : items) {
        if (remain <= 0) break;
        ll need = (remain + e - 1) / e;            // 补齐剩余行数要多少分钟
        ll take = min(v, max(u, need));            // 至少 u，至多 v，够用就少买
        H += take;
        remain -= e * take;
    }
    if (remain > 0) return -1;

    const ll NEG = -(1LL << 60);       // "恰好 t 分钟凑不出来"的哨兵
    vector<ll> dp(H + 1, NEG), old(H + 1), g(H + 1), ndp(H + 1);
    vector<int> que(H + 1);            // 单调队列存下标 s，每个 s 至多进队一次
    dp[0] = 0;

    for (auto& [e, u, v] : items) {
        old = dp;
        for (ll s = 0; s <= H; s++)
            g[s] = old[s] - e * s;     // 买它时前面花 s 分钟的"相对划算程度"

        int head = 0, tail = 0, added = -1;
        for (ll t = 0; t <= H; t++) {
            ll best = old[t];          // 不买这个代理，沿用旧值
            if (t >= u) {
                ll right = t - u;
                ll left = t - v < 0 ? 0 : t - v;
                while (added < right) {            // 窗口右端扩一格
                    added++;
                    while (tail > head && g[que[tail - 1]] <= g[added]) tail--;
                    que[tail++] = added;
                }
                while (tail > head && que[head] < left) head++;   // 队头出窗
                if (tail > head) {
                    ll s = que[head];
                    ll cand = old[s] + e * (t - s);  // 买 x = t - s 分钟
                    if (cand > best) best = cand;
                }
            }
            ndp[t] = best;
        }
        dp.swap(ndp);
    }

    for (ll t = 0; t <= H; t++)
        if (dp[t] >= G) return t;
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll c, g;
    if (!(cin >> c >> g)) return 0;
    vector<array<ll, 3>> agents(c);
    for (auto& a : agents) cin >> a[0] >> a[1] >> a[2];
    cout << minMinutes(g, agents) << '\n';
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Solution {
    static final long NEG = -(1L << 60); // "恰好 t 分钟凑不出来"的哨兵

    // 返回覆盖 G 行所需的最少购买分钟数，做不到返回 -1。
    // agents 每行是 {效率 e, 最低消费 u, 最高消费 v}。
    static long minMinutes(long G, long[][] agents) {
        if (G <= 0) return 0;              // 一行都不用覆盖，一分钟都不买

        List<long[]> items = new ArrayList<>();
        long total = 0;
        for (long[] a : agents) {
            long e = a[0], u = a[1], v = a[2];
            if (u <= v) {                  // u > v 的代理买不了，剔除
                items.add(new long[]{e, u, v});
                total += e * v;
            }
        }
        if (total < G) return -1;          // 全买到最高消费也盖不住，无解

        // 按效率从高到低贪心买一个可行方案，总分钟 H 作为 DP 上界
        items.sort((x, y) -> Long.compare(y[0], x[0]));
        long remain = G, H = 0;
        for (long[] it : items) {
            if (remain <= 0) break;
            long e = it[0], u = it[1], v = it[2];
            long need = (remain + e - 1) / e;   // 补齐剩余行数要多少分钟
            long take = Math.min(v, Math.max(u, need)); // 至少 u，至多 v
            H += take;
            remain -= e * take;
        }
        if (remain > 0) return -1;

        long[] dp = new long[(int) (H + 1)];
        long[] old = new long[(int) (H + 1)];
        long[] g = new long[(int) (H + 1)];
        long[] ndp = new long[(int) (H + 1)];
        int[] que = new int[(int) (H + 1)];    // 单调队列存下标 s
        Arrays.fill(dp, NEG);
        dp[0] = 0;

        for (long[] it : items) {
            long e = it[0], u = it[1], v = it[2];
            System.arraycopy(dp, 0, old, 0, dp.length);
            for (int s = 0; s <= H; s++) {
                // g[s] = dp[s] - e*s：买它时前面花 s 分钟有多划算
                g[s] = old[s] - e * s;
            }
            int head = 0, tail = 0, added = -1;
            for (int t = 0; t <= H; t++) {
                long best = old[t];            // 不买这个代理，沿用旧值
                if (t >= u) {
                    int right = (int) (t - u);
                    int left = (int) Math.max(0, t - v);
                    while (added < right) {    // 窗口右端扩一格，队列 g 单调递减
                        added++;
                        while (tail > head && g[que[tail - 1]] <= g[added]) tail--;
                        que[tail++] = added;
                    }
                    while (tail > head && que[head] < left) head++; // 队头出窗
                    if (tail > head) {
                        int s = que[head];
                        long cand = old[s] + e * (t - s); // 买 x = t - s 分钟
                        if (cand > best) best = cand;
                    }
                }
                ndp[t] = best;
            }
            long[] sw = dp; dp = ndp; ndp = sw;
        }

        for (int t = 0; t <= H; t++)
            if (dp[t] >= G) return t;
        return -1;
    }

    public static void main(String[] args) throws IOException {
        // 一次性读入全部字节再切词，避免逐行读太慢
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int c = nextInt(in);
        long g = nextLong(in);
        long[][] agents = new long[c][3];
        for (int i = 0; i < c; i++) {
            agents[i][0] = nextLong(in);
            agents[i][1] = nextLong(in);
            agents[i][2] = nextLong(in);
        }
        System.out.println(minMinutes(g, agents));
    }

    private static int nextInt(DataInputStream in) throws IOException {
        int ret = 0, b;
        while ((b = in.read()) != -1 && (b < '0' || b > '9')) {}
        while (b >= '0' && b <= '9') { ret = ret * 10 + (b - '0'); b = in.read(); }
        return ret;
    }

    private static long nextLong(DataInputStream in) throws IOException {
        long ret = 0; int b;
        while ((b = in.read()) != -1 && (b < '0' || b > '9')) {}
        while (b >= '0' && b <= '9') { ret = ret * 10 + (b - '0'); b = in.read(); }
        return ret;
    }
}

Go

package main

import (
	"bufio"
	"os"
	"strconv"
)

const negInf = -(int64(1) << 60) // "恰好 t 分钟凑不出来"的哨兵

// minMinutes 返回覆盖 G 行所需的最少购买分钟数，做不到返回 -1。
// agents 每项是 [3]int64{效率 e, 最低消费 u, 最高消费 v}。
func minMinutes(G int64, agents [][3]int64) int64 {
	if G <= 0 {
		return 0 // 一行都不用覆盖，一分钟都不买
	}
	items := make([][3]int64, 0, len(agents))
	var total int64
	for _, a := range agents {
		e, u, v := a[0], a[1], a[2]
		if u <= v { // u > v 的代理买不了，剔除
			items = append(items, [3]int64{e, u, v})
			total += e * v
		}
	}
	if total < G {
		return -1 // 全买到最高消费也盖不住，无解
	}

	// 按效率从高到低贪心买一个可行方案，总分钟 H 作为 DP 上界
	sortedList := make([][3]int64, len(items))
	copy(sortedList, items)
	for i := 1; i < len(sortedList); i++ { // 简单插入排序，最多 50 个
		for j := i; j > 0 && sortedList[j][0] > sortedList[j-1][0]; j-- {
			sortedList[j], sortedList[j-1] = sortedList[j-1], sortedList[j]
		}
	}
	var remain, H int64
	remain = G
	for _, a := range sortedList {
		if remain <= 0 {
			break
		}
		e, u, v := a[0], a[1], a[2]
		need := (remain + e - 1) / e          // 补齐剩余行数要多少分钟
		take := need                          // 至多 v
		if take > v {
			take = v
		}
		if take < u { // 一旦买就至少 u
			take = u
		}
		H += take
		remain -= e * take
	}
	if remain > 0 {
		return -1
	}

	dp := make([]int64, H+1)
	old := make([]int64, H+1)
	g := make([]int64, H+1)
	ndp := make([]int64, H+1)
	que := make([]int32, H+1) // 单调队列存下标 s，每个 s 至多进队一次
	for t := int64(0); t <= H; t++ {
		dp[t] = negInf
	}
	dp[0] = 0

	for _, a := range items {
		e, u, v := a[0], a[1], a[2]
		copy(old, dp)
		for s := int64(0); s <= H; s++ {
			// g[s] = dp[s] - e*s：买它时前面花 s 分钟有多划算
			g[s] = old[s] - e*s
		}
		head, tail, added := 0, 0, -1
		for t := int64(0); t <= H; t++ {
			best := old[t] // 不买这个代理，沿用旧值
			if t >= u {
				right := t - u
				left := t - v
				if left < 0 {
					left = 0
				}
				for added < int(right) { // 窗口右端扩一格，队列内 g 单调递减
					added++
					for tail > head && g[que[tail-1]] <= g[added] {
						tail--
					}
					que[tail] = int32(added)
					tail++
				}
				for tail > head && int64(que[head]) < left { // 队头出窗
					head++
				}
				if tail > head {
					s := int64(que[head])
					cand := old[s] + e*(t-s) // 买 x = t - s 分钟
					if cand > best {
						best = cand
					}
				}
			}
			ndp[t] = best
		}
		dp, ndp = ndp, dp
	}

	for t := int64(0); t <= H; t++ {
		if dp[t] >= G {
			return t
		}
	}
	return -1
}

func main() {
	// bufio.Scanner 默认缓冲区对大输入不够，这里直接用 bufio.Reader 逐词读。
	reader := bufio.NewReader(os.Stdin)
	readInt := func() int64 {
		neg := false
		c, err := reader.ReadByte()
		for err == nil && (c == ' ' || c == '\n' || c == '\r' || c == '\t') {
			c, err = reader.ReadByte()
		}
		if err != nil {
			return 0
		}
		if c == '-' {
			neg = true
			c, err = reader.ReadByte()
		}
		var x int64
		for err == nil && c >= '0' && c <= '9' {
			x = x*10 + int64(c-'0')
			c, err = reader.ReadByte()
		}
		if neg {
			x = -x
		}
		return x
	}
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	c := readInt()
	g := readInt()
	agents := make([][3]int64, c)
	for i := int64(0); i < c; i++ {
		agents[i][0] = readInt()
		agents[i][1] = readInt()
		agents[i][2] = readInt()
	}
	writer.WriteString(strconv.FormatInt(minMinutes(g, agents), 10))
	writer.WriteByte('\n')
}

C

#include <stdio.h>
#include <stdlib.h>

typedef long long ll;
#define NEG (-(1LL << 60))   /* "恰好 t 分钟凑不出来"的哨兵 */

/* 返回覆盖 G 行所需的最少购买分钟数，做不到返回 -1。
   e/u/v 是每名代理的效率、最低消费、最高消费数组，c 是代理个数。 */
static ll min_minutes(ll G, const ll* e, const ll* u, const ll* v, int c) {
    if (G <= 0) return 0;               /* 一行都不用覆盖 */

    ll total = 0;
    for (int i = 0; i < c; i++)
        if (u[i] <= v[i]) total += e[i] * v[i];  /* u > v 的买不了，不计入 */
    if (total < G) return -1;           /* 全买到最高消费也盖不住 */

    /* 按效率从高到低贪心买一个可行方案，总分钟 H 作为 DP 上界 */
    int order[64];                      /* C <= 50，开小数组就够 */
    int n = 0;
    for (int i = 0; i < c; i++)
        if (u[i] <= v[i]) order[n++] = i;
    /* 简单选择排序即可，个数最多 50 */
    for (int i = 0; i < n; i++) {
        int best = i;
        for (int j = i + 1; j < n; j++)
            if (e[order[j]] > e[order[best]]) best = j;
        int t = order[i]; order[i] = order[best]; order[best] = t;
    }

    ll remain = G, H = 0;
    for (int i = 0; i < n; i++) {
        if (remain <= 0) break;
        int id = order[i];
        ll need = (remain + e[id] - 1) / e[id];        /* 补齐要多少分钟 */
        ll take = v[id] < need ? v[id] : need;         /* 至多 v，够用就少买 */
        if (take < u[id]) take = u[id];                /* 一旦买就至少 u */
        H += take;
        remain -= e[id] * take;
    }
    if (remain > 0) return -1;

    ll* dp = (ll*)malloc(sizeof(ll) * (H + 1));
    ll* old = (ll*)malloc(sizeof(ll) * (H + 1));
    ll* g = (ll*)malloc(sizeof(ll) * (H + 1));
    ll* ndp = (ll*)malloc(sizeof(ll) * (H + 1));
    int* que = (int*)malloc(sizeof(int) * (H + 1));
    for (ll t = 0; t <= H; t++) dp[t] = NEG;
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        ll ee = e[order[i]], uu = u[order[i]], vv = v[order[i]];
        for (ll t = 0; t <= H; t++) old[t] = dp[t];
        for (ll s = 0; s <= H; s++)
            g[s] = old[s] - ee * s;     /* 买它时前面花 s 分钟有多划算 */

        int head = 0, tail = 0, added = -1;
        for (ll t = 0; t <= H; t++) {
            ll best = old[t];           /* 不买这个代理，沿用旧值 */
            if (t >= uu) {
                ll right = t - uu;
                ll left = t - vv < 0 ? 0 : t - vv;
                while (added < right) { /* 窗口右端扩一格，保持 g 队列单调递减 */
                    added++;
                    while (tail > head && g[que[tail - 1]] <= g[added]) tail--;
                    que[tail++] = added;
                }
                while (tail > head && que[head] < left) head++;  /* 队头出窗 */
                if (tail > head) {
                    ll s = que[head];
                    ll cand = old[s] + ee * (t - s);  /* 买 x = t - s 分钟 */
                    if (cand > best) best = cand;
                }
            }
            ndp[t] = best;
        }
        ll* sw = dp; dp = ndp; ndp = sw;
    }

    ll ans = -1;
    for (ll t = 0; t <= H; t++)
        if (dp[t] >= G) { ans = t; break; }

    free(dp); free(old); free(g); free(ndp); free(que);
    return ans;
}

int main(void) {
    int c;
    ll g;
    if (scanf("%d %lld", &c, &g) != 2) return 0;
    static ll e[64], u[64], v[64];      /* C <= 50，静态数组就够 */
    for (int i = 0; i < c; i++)
        scanf("%lld %lld %lld", &e[i], &u[i], &v[i]);
    printf("%lld\n", min_minutes(g, e, u, v, c));
    return 0;
}

Python

import sys
from operator import add, sub
from itertools import accumulate, islice

NEG = -(1 << 60)  # "恰好 t 分钟凑不出来"的哨兵，远小于任何真实覆盖数


def min_minutes(C, G, agents):
    # 返回覆盖 G 行所需的最少购买分钟数，做不到返回 -1。
    # 参数 C 是代理个数（仅与读入对齐），G 是目标行数，
    # agents 是每名代理的 (效率 e, 最低消费 u, 最高消费 v)。
    if G <= 0:
        # 一行都不需要覆盖，一分钟都不用买。
        return 0
    items = []
    total = 0
    for e, u, v in agents:
        if u <= v:
            # u > v 的代理买不了，直接剔除。
            items.append((e, u, v))
            total += e * v
    if total < G:
        # 全部买到最高消费也盖不住 G，无解。
        return -1
    # 按效率从高到低贪心买一个可行方案，它的总分钟 H 就是 DP 的上界：
    # 最优答案不可能比一个可行方案更差。
    remain = G
    H = 0
    for e, u, v in sorted(items, key=lambda x: -x[0]):
        if remain <= 0:
            break
        need = (remain + e - 1) // e   # 按这个效率补齐剩余行数要多少分钟
        take = min(v, max(u, need))    # 至少 u，至多 v，够用就少买
        H += take
        remain -= e * take
    if remain > 0:
        return -1
    # dp[t]：恰好花 t 分钟能覆盖的最大行数，NEG 表示这个总数凑不出来。
    dp = [NEG] * (H + 1)
    dp[0] = 0
    for e, u, v in items:
        w = v - u + 1                  # 决策窗口里有 w 种买法
        # g[s] = dp[s] - e*s：要买这个代理时，前面已花 s 分钟有多划算。
        # 不可达状态带着负哨兵，减去 e*s 后仍是极小值，自然被最大值淘汰。
        g = list(map(sub, dp, range(0, e * (H + 1), e)))
        # 在 g 前面补 w-1 个哨兵：t 较小时窗口左端越界的部分落在哨兵上，
        # 等价于把窗口左端卡在 0，不用分两类讨论。
        gp = [NEG] * (w - 1) + g
        # R[k] = max(gp[k..k+w-1])，对应 t = u+k 时窗口 [t-v, t-u] 的最大值。
        if w == 1:
            R = gp
        elif w <= 64:
            # 窗口窄时把 w 个错位序列逐元素取大，map 在 C 层完成，最快。
            R = list(map(max, *(islice(gp, k, None) for k in range(w))))
        else:
            # 窗口宽时用 van Herk 分块法：块长恰为窗口宽 w，
            # 长度为 w 的窗口 = 块内"从 j 到块尾的后缀最大值" 与
            # "下一位置块头到 j+w-1 的前缀最大值"拼起来，每块只扫两遍。
            m = len(gp)
            nblocks = (m + w - 1) // w
            padded = gp + [NEG] * (nblocks * w - m)
            pre = []                   # 块内前缀最大值
            suf = []                   # 块内后缀最大值
            for i in range(0, nblocks * w, w):
                block = padded[i:i + w]
                pre.extend(accumulate(block, max))
                suf.extend(reversed(list(accumulate(block[::-1], max))))
            R = list(map(max, suf, islice(pre, w - 1, None)))
        # 买它 x = t - s 分钟时覆盖 = e*t + 窗口最大值，这里 t = u + k。
        buy = map(add, R, range(e * u, e * u + e * (H + 1), e))
        # 不买则沿用旧 dp[t]；两者取大。t < u 的前缀只能沿用旧值。
        dp = dp[:u] + list(map(max, dp[u:], buy))
    for t in range(H + 1):
        if dp[t] >= G:
            return t
    return -1


def main():
    data = sys.stdin.buffer.read().split()
    c, g = int(data[0]), int(data[1])
    agents = []
    pos = 2
    for _ in range(c):
        agents.append((int(data[pos]), int(data[pos + 1]), int(data[pos + 2])))
        pos += 3
    print(min_minutes(c, g, agents))


if __name__ == "__main__":
    main()