Một đêm nọ, một tên trộm nọ quyết định đột nhập vào một siêu thị nọ. Siêu thị có ~N~ đồ vật, vật thứ ~i~ có trọng lượng ~A_i~, giá trị ~B_i~. Tên trộm mang theo một cái túi chứa được trọng lượng tối đa ~W~. Hỏi tổng giá trị tối đa tên trộm có thể lấy được là bao nhiêu?

Input

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~W~ (~1 \leq N, W \leq 10^3~).
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~A_i~ và ~B_i~ (~A_i, B_i \leq 10^3~).

Output

• In ra tổng giá trị lớn nhất có thể được lấy đi.

Sample Test

Input:

5 15
12 4
2 2
1 1
1 2
4 10

Output:

15

Bạn được cho một mảng chứa ~n~ số nguyên dương.

Nhiệm vụ của bạn là chia mảng thành ~k~ đoạn con sao cho tổng lớn nhất trong một đoạn con là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~: kích thước của mảng và số đoạn con trong phép chia.
• Dòng tiếp theo chứa ~n~ số nguyên ~x_1, x_2, \dots, x_n~: nội dung của mảng.

Output

In ra một số nguyên duy nhất: tổng lớn nhất trong một đoạn con của phép chia tối ưu.

Constraints

• ~1 \leq n \leq 2 \cdot 10^5~
• ~1 \leq k \leq n~
• ~1 \leq x_i \leq 10^9~

Sample Test