No.3013 ハチマキ買い星人
タグ : / 解いたユーザー数 167
作問者 :
Apollo@Kuro
/ テスター :
高橋ゆに
👑 
loop0919
eom2357
DeltaStruct
Yama.can
こめだわら
のらら
あじゃじゃ
👑 
binap
問題文
岩井星人さんはハチマキを買い足しに、$Y$ 円を持った状態で故郷の大阪府岩井星に戻りました。
岩井星には $N$ 個の街があり、それぞれ $1, 2, \ldots, N$ の番号が付いています。現在、岩井星人さんは空港のある街 $1$ に居ます。
また、岩井星には街と街をつなぐ $M$ 本の道路が存在します。
$i$ 番目の道路は街 $A_i$ と街 $B_i$ を双方向につないでおり、移動している最中に悪い人から $C_i$ 円カツアゲされてしまいます。
所持金が $X$ 円の状態でカツアゲされると、所持金が $\max(X - C_i, 0)$ 円になります。
また、岩井星には $P$ 軒の店があり、$i$ 番目の店は街 $D_i$ に存在し、$1$ 本あたり $E_i$ 円でハチマキを売っています。
店では、所持金の限り好きなだけ $0$ 本以上のハチマキを買うことができます。
ただし、$1$ つの街に存在する店は $1$ 軒以下です。
このとき、岩井星人さんは街 $1$ から出発し、どれだけ多くのハチマキを買うことができるでしょうか？
制約
- $2 \leq N \leq 2 × 10^5$
- $1 \leq M \leq \min \left(2 × 10^5, \dfrac{N(N-1)}{2} \right)$
- $1 \leq A_i < B_i \leq N\ (1 \leq i \leq M)$
- $(A_i, B_i) \neq (A_j, B_j)\ (1 \leq i < j \leq M)$
- $1 \leq C_i \leq 10^9\ (1 \leq i \leq M)$
- $1 \leq P \leq N$
- $1 \leq D_i \leq N\ (1 \leq i \leq P)$
- $D_i \neq D_j\ (1 \leq i < j \leq P)$
- $1 \leq E_i \leq 10^9\ (1 \leq i \leq P)$
- $1 \leq Y \leq 10^{18}$
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N\ M \ P\ Y$ $A_1\ B_1\ C_1$ $A_2\ B_2\ C_2$ $\vdots$ $A_M\ B_M\ C_M$ $D_1\ E_1$ $D_2\ E_2$ $\vdots$ $D_P\ E_P$
出力
岩井星人さんが買えるハチマキの最大数を出力せよ。
サンプル
サンプル1
入力
3 3 2 19 1 3 4 2 3 1 1 2 5 2 5 3 4
出力
3
はじめ、岩井星人さんは $19$ 円を持っています。
街 $1$ から街 $2$ へ移動するときに $5$ 円カツアゲされた後、街 $2$ でハチマキを $1$ 本買います。
そこから $1$ 円カツアゲされながら街 $3$ に移動してハチマキを$2$本買うことで、合計 $3$ 本買うことができるため3と出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。