723 . 打工仔
TopCoder
Tags
Description
魯夫的夢想是成為航海王，但長榮跌下來以後他就跟身邊的韭菜一樣被割了，現在只能睡公園的紙箱。
為了重新找回他的夢想，他要打一些奇怪的工籌措資金。
因為公園不好睡，魯夫每天打完工以後他會直接在打工的地點過夜。
現在有 $n$ 間公司可以給魯夫打工且這些公司在同一條直線上，公司由近到遠編號 $1, 2, 3, \ldots, n$，並且從公園到第一間公司需要花 $t_1$ 天時間，從第 $i-1$ 間公司到第 $i$ 間公司需要花 $t_i$ 天時間。
而這些公司特別黑心，會紀錄魯夫總共來了幾天然後依據這個次數扣他的薪水。假設第 $i$ 個公司給你的初始薪水是 $M_i$，他在此公司工作第 $i$ 天時只會給你 $M_i - (i - 1)\cdot D_i$ 的薪水。請你幫魯夫算一下他在 $T$ 天之內最多可以賺到多少錢？
Input Format
輸入第一行有兩個整數 $T, n$，第二行有 $n$ 個整數 $M_i$，第三行有 $n$ 個整數 $D_i$，第四行有 $n$ 個整數 $t_i$。整數之間以空白分隔。其中保證：
- $0 \leq T, n, M_i, D_i, t_i \leq 10^ 5$
- $nT \leq 10^ 7$
Output Format
輸出魯夫在第 $T$ 天能賺到的錢的最大值。
Sample Input 1
12 2
10 1
2 5
0 2
10 1
2 5
0 2
Sample Output 1
31
Sample Input 2
48 4
10 15 20 17
0 3 4 3
0 1 2 3
10 15 20 17
0 3 4 3
0 1 2 3
Sample Output 2
480
Hints
Problem Source
TIOJ 1399
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~10 | $t_i=0$ | 20 |
| 3 | 0~29 | 無額外限制 | 80 |