問題一覧 > 通常問題

No.2492 Knapsack Problem?

レベル : / AI推定難易度 : 101 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 236
作問者 : KumaTachiRen / テスター : hiro1729
お気に入りにしたユーザー ProblemId : 9065 / 自分の提出
問題文最終更新日: 2023-10-02 17:19:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 407 (順位表) の他の問題:

Problem Statement

Alice has come to a knapsack shop to buy a knapsack. The shop sells $N$ knapsacks, and the $i\ (1\leq i\leq N)$-th knapsack has capacity $v_i$ and weight $w_i$.

Alice wants a knapsack with as large a capacity as possible that is also not too heavy.

Find the capacity of the knapsack with the maximum capacity among the knapsacks with weight at most $W$. However, if there is no knapsack with weight at most $W$, output -1.

Input

$N\ W$
$v_1\ w_1$
$v_2\ w_2$
$\vdots$
$v_N\ w_N$

  • $1\leq N\leq 1000$
  • $1\leq W\leq 1000$
  • $1\leq v_i\leq 1000$
  • $1\leq w_i\leq 1000$
  • All inputs are integers.

Output

If there exist knapsacks with weight at most $W$, output the maximum capacity among them; otherwise, output -1. Print a newline at the end.

Sample

Sample 1
Input
3 7
6 9
3 3
5 6
Output
5

The knapsacks with weight at most $7$ are the $2,3$-th ones, and the maximum volume among them is $5$, that of the $3$-rd knapsack.

Sample 2
Input
3 14
1 59
2 65
3 58
Output
-1

There is no knapsack with weight at most $14$, so output -1.

Sample 3
Input
10 414
851 708
305 850
438 421
245 191
409 476
764 490
159 386
350 505
531 42
292 822
Output
531

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