思路与算法

设交付时间为t。技术人员i若完成第一个软件x个模块，第二个软件最多完成floor((t-xd1_i)/d2_i)个，前提是xd1_i<=t。由于同一人员每次只能做一个模块，其两类模块总耗时不超过t；不同人员可以同时工作。

用分组动态规划检查t。dp[a]表示处理若干人员后，恰好完成a个第一软件模块时，最多能完成的第二软件模块数，不可达记-1。初始dp[0]=0。每个人员单独建立next，从旧dp枚举其x，第二模块取可做的最大值，更新next[a+x]，数量截断到m。使用完当前人员后整体替换dp，避免在同一层重复使用该人员。若dp[m]>=m，就能完成两个软件。

时间增大不会减少每个人员的可选分配，判定单调。下界0，上界取某一个人员独自完成两软件各m模块的时间m*(d1+d2)之最小值。二分第一个可行交付时刻。

正确性说明

给定t，一个人员的分配(x,y)可执行，当且仅当xd1+yd2<=t：必要性来自同一人不能并行，充分性可将其全部模块依次完成。人员间模块相互独立，所以各人的合法分配可以同时从时刻0执行，最晚不超过t。

对相同第一模块数a，仅保留最大的第二模块数不会丢失可行解。更多第二模块不会占用其他人员资源；若超过目标m，可以删去多余模块而缩短时间。因此每个人员固定x后取其最大y是支配选择。转移遍历所有合法x，且只读前一组dp；按已处理人员数归纳，dp准确表示所有分配中的最大第二模块数。dp[m]>=m当且仅当存在完成两类目标的整体分配。

已有t内的方案在更大时间仍可执行，所以可行性为整数后缀。选定的上界能由单个人员完成两类各m个模块，其余人员空闲，必可行。二分按准确判定缩小闭区间，终止得到最小可行整数t，即最早交付时间。

复杂度

单次判定初始化dp与每个next各O(M)，每个人员至多遍历M+1个已完成数量和M+1个当前选项，总时间O(NM²)，额外空间O(M)。读取人员O(N)。上界U<=20000，二分O(log(U+1))次，含清零初始化总时间O(NM²*log(U+1)+N)，总额外空间O(N+M)。所有模块数与耗时在int范围内。

易错点

1. 两个软件都各有m个模块，不是总共m个。
2. 不同技术人员可并行，同一人员的两类模块耗时需要相加，不能取最大值。
3. 分组转移必须用新数组，原地更新会把同一个人重复使用。
4. 不可达状态为-1；第二软件数量可以截断到m，避免无意义扩大状态。
5. 不预设每个人只做一种软件。覆盖单人、全部100人、模块数100、工时100、相反特长与公开样例。

参考代码（C++11）

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n);
    int hi = 20000;
    for (auto &x : a) {
        cin >> x.first >> x.second;
        hi = min(hi, m * (x.first + x.second));
    }
    auto ok = [&](int t) {
        vector<int> dp(m + 1, -1);
        dp[0] = 0;
        for (auto w : a) {
            vector<int> next(m + 1, -1);
            for (int old = 0; old <= m; ++old)
                if (dp[old] >= 0)
                    for (int x = 0; x <= m - old && x * w.first <= t; ++x) {
                        int b = (t - x * w.first) / w.second;
                        next[old + x] = max(next[old + x], min(m, dp[old] + b));
                    }
            dp.swap(next);
            if (dp[m] >= m)
                return true;
        }
        return false;
    };
    int lo = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    cout << lo << '\n';
}