人力分配 (APCS 2020-10 初級)

有一個公司有 \(n\) 個員工，還有兩個工廠。如果工廠一與工廠二分別有 \(X_1\) 與 \(X_2\) 個員工，兩個工廠的收益 \(Y_1\)、\(Y_2\) 分別會是

請你考慮所有分配員工的方式，找出收益最大的組合，輸出最大收益。注意，每個員工皆需分配到其中一個工廠（即 \(X_1 + X_2 = n\)，且 \(X_1, X_2 \ge 0\)；其中一個工廠也可以分配到 \(0\) 個員工）。

輸入格式

第一行有三個整數 \(A_1\)、\(B_1\)、\(C_1\)。

第二行有三個整數 \(A_2\)、\(B_2\)、\(C_2\)。

第三行有一個正整數 \(n\)。

限制

• \(1 \le n \le 100\)
• \(-1000 \le A_1, B_1, C_1, A_2, B_2, C_2 \le 1000\)

輸出格式

輸出最大收益（可能為負數）。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過的測試資料筆數給分。其中：

• 第 1 子題組（\(50\) 分）：\(n = 2\)。
• 第 2 子題組（\(50\) 分）：\(1 \le n \le 100\)。

範例輸入

2 -1 3
4 -5 2
2

範例輸出

11

（說明）\(n = 2\)。若 \(X_1 = 0, X_2 = 2\)：\(Y_1 = 3\)、\(Y_2 = 4 \cdot 4 - 5 \cdot 2 + 2 = 8\)，合計 \(11\)；若 \(X_1 = 2, X_2 = 0\)：\(Y_1 = 2 \cdot 4 - 2 + 3 = 9\)、\(Y_2 = 2\)，合計 \(11\)。最大收益為 \(11\)。

題目來源

APCS 2020 年 10 月實作題第 1 題。

• ZeroJudge f312