No.2859 Falling Balls
タグ : / 解いたユーザー数 19
作問者 :
Problem Statement
Yakitori-kun is at coordinate $0$ on a number line at time $0$.
For each $t = 0, 1, 2, \dots$, letting $u$ be his coordinate at time $t$, Yakitori-kun moves to a coordinate between $u-K$ and $u+K$, inclusive, at exactly time $t+0.5$.
Now, $N$ balls will fall.
The $i$-th ball falls at coordinate $X_i$ at time $T_i$. If Yakitori-kun is at coordinate $X_i$ at exactly time $T_i$, he can catch the $i$-th ball, and catching it gives him a score of $C_i$.
Find the maximum score Yakitori-kun can obtain by acting appropriately.
Constraints
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq K \leq 10^{9}$
- $1 \leq T_i \leq 10^{9}$
- $| X_i | \leq 10^{9}$
- $1 \leq C_i \leq 10^{9}$
- $(T_1, X_1), (T_2, X_2), \dots, (T_N, X_N)$ are all distinct.
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $K$ $T_1$ $T_2$ ... $T_N$ $X_1$ $X_2$ ... $X_N$ $C_1$ $C_2$ ... $C_N$
Output
Output the answer to the problem on a single line.
Sample
Sample 1
Input
3 2 1 2 3 -1 2 4 5 3 4
Output
7
For example, a score of $7$ can be achieved by acting as follows.
- Move to coordinate $1$ at time $0.5$.
- Move to coordinate $2$ at time $1.5$.
- Catch the $2$-nd ball at time $2$, gaining a score of $3$.
- Move to coordinate $4$ at time $2.5$.
- Catch the $3$-rd ball at time $3$, gaining a score of $4$.
- Make no moves from time $3.5$ onward.
Sample 2
Input
8 5 3 85 69 67 63 90 24 38 55 11 -18 -71 -96 -5 10 40 92 95 79 31 1 48 98 43
Output
363
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。