372. Tea Party
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
Alice organizes a tea party for her classmates. There are
K guests on this party and
N types of tea of two kinds: black and green. During each party round, all guests who are currently present on the party get one bag of the same type of tea. After each party round, one of the guests leaves the party because he/she needs to meet somebody elsewhere. Alice needs to minimize the total cost of tea bags spent, but she also wants to make it so that all served tea types must be different, and any three consecutive rounds of the party are not using tea of the same kind. Help her.
Input
The first line of the input contains two integers
K and
N (1≤
K,
N ≤ 1000).
N lines follow, each for one tea type, containing two integers
c_{i} and
s_{i} each (
), where
c_{i} is the cost of one bag of
ith type, and
s_{i} is zero for green tea and one for black tea.
Output
Output any possible optimal party plan —
K different numbers between 1 and
N, each for one type of tea. If it is impossible to organize the party, output "
Impossible
" without quotes.
Example(s)
sample input

sample output

3 4
1 0
2 0
4 1
3 1

1 2 4
