Ba Lô Theo Tổng Giá Trị · canuc80k1226

Có $N$ vật khác nhau. Vật thứ $i$ có trọng lượng $W_{i}$ và giá trị $V_{i}$ ; mỗi vật chỉ được chọn nhiều nhất một lần. Một ba lô chịu được tổng trọng lượng không vượt quá sức chứa $C$ . Hãy tìm tổng giá trị lớn nhất của một tập vật có thể đặt vào ba lô. Bạn được phép không chọn vật nào, và không bắt buộc dùng hết sức chứa.

Input

Dòng đầu chứa hai số nguyên $N$ và $C$ .
$N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $W_{i}$ và $V_{i}$ .

Output

In một số nguyên: tổng giá trị lớn nhất có thể đạt được.

Constraints

$1 \leq N \leq 100$ .
$1 \leq C \leq 1 0^{9}$ .
$1 \leq W_{i} \leq C$ với mọi $i$ .
$1 \leq V_{i} \leq 1000$ với mọi $i$ .
Các vật có cùng trọng lượng hoặc cùng giá trị vẫn là những vật riêng biệt; mỗi vật được dùng nhiều nhất một lần.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 20$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Chọn vật thứ nhất và thứ hai: tổng trọng lượng $6 + 4 = 10$ , tổng giá trị $8 + 5 = 13$ . Các tập hợp hợp lệ khác đều có tổng giá trị không vượt quá $13$ .

Ý tưởng: Tổng giá trị không vượt 100·1000=100000, nhỏ hơn rất nhiều so với sức chứa. Đặt dp[x] là tổng trọng lượng nhỏ nhất để đạt đúng giá trị x bằng các vật đã xét. Khởi tạo dp[0]=0, các trạng thái khác là vô cùng. Với vật (w,v), duyệt x giảm và cập nhật dp[x]=min(dp[x],dp[x-v]+w).
Chứng minh tính đúng đắn: Với một tổng giá trị x sau khi xét vật mới, phương án tối ưu hoặc bỏ vật ấy, giữ trạng thái cũ, hoặc lấy nó và ghép với một phương án đạt x-v chỉ từ các vật trước. Lưu trọng lượng nhỏ nhất là đủ vì trong cùng một giá trị, phương án nhẹ hơn luôn trội hơn phương án nặng hơn cho mọi lựa chọn sau. Duyệt x giảm bảo đảm trạng thái nguồn chưa dùng vật hiện tại. Quy nạp theo số vật chứng minh DP chính xác; giá trị lớn nhất có trọng lượng không vượt C là đáp án.
Độ phức tạp: Gọi S=ΣV_i≤100000; thời gian O(N·S) và bộ nhớ O(S).