問題一覧 > 通常問題

No.3013 ハチマキ買い星人

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 167
作問者 : Apollo@KuroApollo@Kuro / テスター : 高橋ゆに高橋ゆに 👑 loop0919loop0919 eom2357eom2357 DeltaStructDeltaStruct Yama.canYama.can こめだわらこめだわら のららのらら あじゃじゃあじゃじゃ 👑 binapbinap
5 ProblemId : 11625 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-01-25 11:24:34

問題文

岩井星人さんはハチマキを買い足しに、$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もしくは右上の雲マークをクリックしてアカウントを作成してください。