Cho N cái túi, cái túi thứ i có trọng lượng wi và giá trị vi. Gọi M là tổng trọng lượng của N cái túi. Đưa ra M số, số thứ i là tổng giá trị lớn nhất có thể của 1 tập hợp các cái túi từ 1 đến N mà tổng trọng lượng các túi được chọn không vượt quá i.
INPUT:
_ Dòng 1: Số nguyên N. (1 <= N <= 10^5)
_ N dòng tiếp theo, mỗi dòng gồm 2 số nguyên W và V. (1 <= W <= 2; 1 <= V <= 10^9)
_ Với i = 1, ta chọn tập hợp cái túi {1} với tổng giá trị là 1.
_ Với i = 2, ta chọn tập hợp cái túi {5} với tổng giá trị là 5.
_ Với i = 3, ta chọn tập hợp cái túi {1,5} với tổng giá trị là 6.
_ Với i = 4, ta chọn tập hợp cái túi {4,5} với tổng giá trị là 9.
_ Với i = 5, ta chọn tập hợp cái túi {1,4,5} với tổng giá trị là 10.
_ Với i = 6, ta chọn tập hợp cái túi {3,4,5} với tổng giá trị là 12.
_ Với i = 7, ta chọn tập hợp cái túi {1,3,4,5} với tổng giá trị là 13.
_ Với i = 8, ta chọn tập hợp cái túi {2,3,4,5} với tổng giá trị là 14.
_ Với i = 9, ta chọn tập hợp cái túi {1,2,3,4,5} với tổng giá trị là 15.