Bài tập ngày 22/4

Ba lô

Time limit: 1.0 / Memory limit: 256M

Point: 10

Có $N$ viên đá quý được đánh số từ 1 đến $N$ . Viên thứ $i$ ( $1 \leq i \leq N$ ) có khối lượng là $w_{i}$ và giá trị là $v_{i}$ .

Nam định chọn một số viên bỏ vào chiếc túi của anh ta để 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ị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Input

Dòng đầu tiên chứa hai số nguyên $N$ ( $1 \leq N \leq 100$ ) và $W$ ( $1 \leq W \leq 10^{5}$ ): số lượng viên đá 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 \leq w_{i} \leq W$ ) và $v_{i}$ ( $1 \leq v_{i} \leq 10^{9}$ ) — lần lượt là khối lượng và giá trị của viên đá thứ $i$ .

Output

Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Ví dụ

Input

Copy

Output

Copy

Giải thích:

Chọn viên đá thứ nhất và thứ 3, chúng có trọng lượng là 3+5=8 vừa với chiếc túi và giá trị là 30+60=90.

Ba lô

Nộp bài

Time limit: 1.0 / Memory limit: 256M

Point: 10

Có $N$ viên đá quý được đánh số từ 1 đến $N$ . Viên thứ $i$ ( $1 \leq i \leq N$ ) có khối lượng là $w_{i}$ và giá trị là $v_{i}$ .

Hãy tìm tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà. Biết rằng Nam được lấy một phần của viên đá.

Input

Dòng đầu tiên chứa hai số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ) và $W$ ( $1 \leq W \leq 10^{3}$ ): số lượng viên đá 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 \leq w_{i} \leq W$ ) và $v_{i}$ ( $1 \leq v_{i} \leq 10^{9}$ ) — lần lượt là khối lượng và giá trị của viên đá thứ $i$ .

Output

Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà. Kết quả làm tròn đến số nguyên.

Ví dụ

Input

Copy

Output

Copy

Giải thích:

Chọn viên đá thứ hai và 4/5 phần viên đá thứ 3, chúng có trọng lượng là 4 + 5 * 4/5 = 8 vừa với chiếc túi và giá trị là 50 + 60 * 4/5 = 98.

Ba lô

Nộp bài

Time limit: 1.0 / Memory limit: 256M

Point: 10

Có $N$ loại viên đá quý được đánh số từ 1 đến $N$ . Loại viên thứ $i$ ( $1 \leq i \leq N$ ) có khối lượng là $w_{i}$ , giá trị là $v_{i}$ và số lượng rất lớn, được xem như là vô hạn.

Hãy tìm tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Input

Dòng đầu tiên chứa hai số nguyên $N$ ( $1 \leq N \leq 100$ ) và $W$ ( $1 \leq W \leq 10^{3}$ ): số lượng loại đá 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 \leq w_{i} \leq W$ ) và $v_{i}$ ( $1 \leq v_{i} \leq 10^{9}$ ) - lần lượt là khối lượng và giá trị của loại viên đá thứ $i$ .

Output

Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Ví dụ

Input

Copy

Output

Copy

Giải thích:

Chọn 2 viên đá loại 2, chúng có trọng lượng là 4 * 2=8 vừa với chiếc túi và giá trị là 50 * 2=100.