問題一覧 > 通常問題

No.2161 Black Market

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 38
作問者 : AngrySadEightAngrySadEight / テスター : tko919tko919
1 ProblemId : 8864 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-09 02:59:33

問題文

$N$ 枚のカードがあります.それぞれのカードにはコスト価値の2つの指標があり,$i$ 番目のカードのコストは $A_i$,価値は $B_i$ です.

あなたは,これら $N$ 枚のカードの中から $K$ 枚以下のカードを選んで持っていき,闇市場に向かいます.ただし,持っていくカードのコストの総和は,$L$ 以下である必要があります.このとき,持っていくカードの価値の総和が $P$ 以上であれば,またそのときに限り,取引が成功します.

取引を成功させることのできるカードの選び方は何通りあるか,求めてください.

なお,「2つの選び方が異なる」とは,「あるカードが存在して,2つの選び方のうちの一方では選ばれており,他方では選ばれていない」ことを指します.

制約

  • 入力はすべて整数である.
  • $1 \leq N \leq 34$
  • $1 \leq K \leq N$
  • $1 \leq L,P \leq 10^9$
  • $1 \leq A_i,B_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる.

$N$ $K$ $L$ $P$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

答えを出力せよ.

サンプル

サンプル1
入力
4 2 4 5
1 2
2 3
3 4
4 5
出力
3

$1$ 番目のカードと $2$ 番目のカードを選ぶと,コストの合計が $3$ に,価値の合計が $5$ となるため,取引が成功します.その他,$1$ 番目のカードと $3$ 番目のカードを選ぶやり方や,$4$ 番目のカードのみを選ぶやり方でも取引は成功します.

一方,$2$ 枚目のカードと $3$ 枚目のカードを選ぶやり方だと,価値の合計は $7$ となりますが,コストの合計が $5$ となってしまい,コストの合計が $4$ 以下でなければならない条件に反することに注意してください.

サンプル2
入力
5 5 10 10
2 2
2 2
2 2
2 2
2 2
出力
1

カードを全て選ばないと,取引は成功しません.

サンプル3
入力
18 5 100 2022
35 890
35 1016
6 9
6 1341
6 398
6 500
6 495
7 406
11 310
11 514
128 321
13 210
13 35
14 99
14 884
18 340
18 1127
18 109
出力
5646

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。