PROBLEM • vnojatcoderdpd

VNOJ - atcoder_dp_d: Atcoder Educational DP Contest D - Knapsack 1

VNOJ - atcoder_dp_d
Viewing statement: System (English)
Chưa kết nối tài khoản Virtual Judge (VJudge) Tài khoản của bạn chưa kết nối hoặc phiên đăng nhập VJudge đã hết hạn, do đó đề bài có thể bị lỗi hiển thị và không thể nộp bài.

VNOJ - atcoder_dp_d: Atcoder Educational DP Contest D - Knapsack 1

Đề bài được nhập từ Virtual Judge: VNOJ - atcoder_dp_d

Có \(N\) đồ vật được đánh số từ \(1\) đến \(N\). Đồ vật thứ \(i\) \((1 \le i \le N)\) có khối lượng là \(w_i\) và giá trị là \(v_i\).

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là \(W\), nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là \(W\).

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

Dòng đầu tiên chứa hai số nguyên \(N\) \((1 \le N \le 100)\) và \(W\) \((1 \le W \le 10^5)\): số lượng đồ vật và sức chứa tối đa của chiếc túi.

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i\) \((1 \le w_i \le W)\) và \(v_i\) \((1 \le v_i \le 10^9)\) lần lượt là khối lượng và giá trị của đồ vật thứ \(i\).

Output

Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Sample 1

Input
3 8
3 30
4 50
5 60
Output
90

Chọn đồ vật \(1\) và \(3\). Tổng khối lượng sẽ là \(3 + 5 = 8\) và tổng giá trị là \(30 + 60 = 90\).

Sample 2

Input
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
Output
5000000000

Kết quả có thể vượt quá giới hạn kiểu số nguyên \(32\)-bit.

Sample 3

Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17

Chọn đồ vật \(2\), \(4\) và \(5\). Tổng khối lượng sẽ là \(5 + 6 + 3 = 14\) và tổng giá trị là \(6 + 6 + 5 = 17\).

                <hr>
        </div>
<div class="problem-tabs">
    <ul>
        <li><a href="#comments" class="active">Bình luận</a></li>
    </ul>
</div>


<div id="comments" class="tab-content active"
     data-comments-url="/problem/atcoder_dp_d/comments" data-comments-trigger="tab"
     data-comments-preloaded="false">
        <div class="comments-loading">Đang tải...

Comments

There are no comments at the moment.