0737 - 力のコーヒー (Power Coffee)

ストーリー

都市NOW_MAN_ZAWでは「力のコーヒー」がバカ売れしている。 「力のコーヒー」とは、魔法かと思うくらいに力が湧いてくるコーヒーであり、 その都市の各社はそれの製作に励んでいた。 そのおかげで、宅配をする会社も大繁盛という結果で、 宅配する会社がやけに増えた。 「力のコーヒー」はまさしく、 都市経済の柱 と化したのだった。

問題

現在、「力のコーヒー」を宅配する会社は $N$ 社ある。

会社の拠点は、それぞれ $( X_i, Y_i )$ にある。子会社は存在せず、一拠点に限る。

あなたは都市NOW_MAN_ZAWに家があり、そこに住んでいる。その座標は $( sx , sy )$ である。

この都市は、正方形の区画ですべての物件が区切られているので、斜めの移動はできない。
したがって、あなたの家からある会社の拠点までの宅配時間は、$ | sx - X_i | + | sy - Y_i | $ である。
( 「 | 」で囲まれている値は絶対値となる。 )

あなたは力がほしいため、時間 $T$ だけ集中して各社に「力のコーヒー」を注文しようとしている。
コーヒーは注文した時間に発送され、それから宅配時間だけ過ぎた時に、家に届く。
時間 $0$ から時間 $T$ までの間、注文ができるが、家に届けられる時間が $T$ を過ぎてはならない。
すなわち、注文できる時間は $[0$, $T]$ ということになる。

あなたは任意の宅配をする会社に電話をかけて注文ができる。
電話をかけた瞬間に注文ができ、電話も直ちに終了する。
ただし電話をした後時間 $K$ だけ経たなければ、次の電話ができない。
すなわち、次の注文は、現在の注文から時間 $K$ 過ぎた後でしかできない。

各社の売っている「力のコーヒー」は、それぞれ力がつくパラメータ (飲んでどれぐらい力がつくか) が異なるため、
時間 $T$ までに、パラメータ(以後パラメータと呼ぶ)の総和が最大になるように「力のコーヒー」を集めたい。

パラメータは $ P_i $ で表される。

また、一つの会社には一つだけ商品を頼め、それ以後、その店の注文はできないものとする。

課題　

時間 $T$ の間で、手に入れられる最大の、パラメータの総和を求めよ。

入力

$1$ 行目に「力のコーヒー」を宅配する会社の数 $N$, 時間 $T$, 注文にかかる時間 $K$ が与えられる。

$2$ 行目にあなたの家の座標 $sx$ , $sy$ が与えられる。

$3$ ~ $(2 + N)$ 行目に、それぞれの会社の拠点 $X_i$ , $Y_i$, パラメータ $P_i$ が与えられる。

$N$ $T$ $K$
$sx$ $sy$
$X_1$ $Y_1$ $P_1$
$X_2$ $Y_2$ $P_2$
   .
   .
   .
$X_N$ $Y_N$ $P_N$

出力

時間 $T$ の間で、手に入れられる最大の、パラメータの総和を一行に出力せよ。

制約

• $1 \leq N \leq 1000$
• $1 \leq T, K \leq 10^6$
• $-10^6 \leq sx, sy, X_i, Y_i \leq 10^6 ( 1 \leq i \leq N )$
• $1 \leq P_i \leq 10^6$
• あなたの家の座標、各社の座標が同じになることはない。

入出力例

入力例1

6 25 5
0 0
10 9 9
-4 6 10
-9 -9 10
2 3 20
10 -5 30
-5 -5 40

出力例1

110

解説

時間0に3番目, 時間5に2番目, 時間10に5番目, 時間15に6番目, 時間20に4番目。
この順に注文すると、最大のパラメータ110を得ることが出来る。
家に届けられる時間はそれぞれ、18, 15, 25, 25, 25ですべて間に合っている。

入力例2

5 25 8
4 5
-9 3 3
-15 -13 9
10 2 4
5 2 3
10 5 6

出力例2

13

コメント

1年生もじゃんじゃん解いてね！！！

一応貪欲タグに入れているけど、大丈夫だよね

2018 5/29 ソースコードを公開しました