Tổng K

View as PDF

Submit solution

Points: 2000 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho 2 mảng ab gồm n phần tử gồm các số nguyên không âm và số nguyên dương k.

Ở mỗi thao tác bạn có quyền chọn 1 số có giá trị i (1 \leq i \leq n) sau đó hoán đổi giá trị a_{i}b_{i}.

Nhiệm vụ của bạn là tìm số thao tác nhỏ nhất để \sum_{i=1}^{n} a_{i} có giá trị bằng j (với j là các số tự nhiên từ 1 đến k).

Input

  • Dòng đầu tiên gồm số nk (1 \leq n, k \leq 10^{5}).
  • Trong n dòng tiếp theo, dòng thứ i chứa 2 số a_{i}b_{i} (1 \leq \sum_{i = 1}^{n} (a_{i} + b_{i}) \leq 2 \times 10^{5}).

Output

  • Gồm k dòng, dòng thứ j in ra số lượng thao tác ít nhất để \sum_{i=1}^{n} a_{i} có giá trị bằng j, nếu không tồn tại cách nào thì in ra -1.

Scoring

  • Subtask 1 (50\% số điểm): 1 \le n, k \le 2000, 1 \le \sum_{i =1}^{n} (a_{i} + b_{i}) \le 2000.
  • Subtask 2 (50\% số điểm): Không có rằng buộc gì thêm.

Example

Test 1

Input
3 5
1 3
2 5
0 7
Output
-1
-1
0
-1
1

Comments

There are no comments at the moment.