Submit solution
Points:
2000 (partial)
Time limit:
1.5s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem types
Cho 2 mảng a và b 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} và 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ố n và k (1 \leq n, k \leq 10^{5}).
- Trong n dòng tiếp theo, dòng thứ i chứa 2 số a_{i} và 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