U244424 01分数不规划（渐入佳境）

$La\_Pluma$ 意识到似乎大家忽略了这个~~没用的~~知识点， 于是出了一道水题提醒大家

### 简要题意 给定 $n$ 个二元组 $\{a_i, b_i\}$， 求一组 $w$（$w_i \in \{0, 1\}$）使得 $$ \frac{\sum_{i = 1}^{n}w_i \times a_i}{\sum_{i = 1}^{n}w_i \times b_i} $$ 最大（需要有至少一个 $w_i = 1$） ### 题目描述 $La\_Pluma$ 小可爱加入战场， 现在一共有 $n$ 个敌人， $La\_Pluma$ 需要分散注意力关注每一个敌人， 众所周知， $La\_Pluma$ 平时注意力非常涣散， ~~甚至可以忽略不计~~， 但战斗时 $La\_Pluma$ 会表现出让人大吃一惊的专注度， 因为 每一个出现的敌人都会提高 $La\_Pluma$ 整体的注意力， 而不同的敌人会需要不同级别的注意 ~~普通士兵显然和大盾不可同日而语）~~ 每一个敌人都有一个值 $a_i$ 表示他的出现会提高 $La\_Pluma$ 多少注意力， 一个值 $b_i$ 表示这个敌人需要多少级别的注意力 $La\_Pluma$ 分配注意力的方法是： 每一个自己面对的敌人 $x$ 可以享受她 $\frac{\sum_{i \in La\_Plma面对的敌人}a_i}{\sum_{i \in La\_Plma面对的敌人}b_i} \times b_x$ 的注意力， 博士不想让 $La\_Pluma$ 太累， 所以希望让 $La\_Pluma$ 尽可能的对于已有敌人注意力更高， 现在博士想要请你算一下， 让 $La\_Pluma$ 阻挡多少敌人可以使得 $\frac{\sum_{i \in La\_Plma面对的敌人}a_i}{\sum_{i \in La\_Plma面对的敌人}b_i}$ 最大， 从而让 $La\_Pluma$ 更加专注于每一个敌人（羽毛笔至少面对一个敌人）

第一行一个数 $n$ ， 接下来 $n$ 行， 每行两个整数 $a_i, b_i$， 表示每一个敌人的两个数值

若无解， 只需要输出一个 $-1$ 否则输出两行 第一行一个数表示答案，保留三位小数 第二行输出一个符合条件的 $w$ 数组， 对应每一个敌人， 若 $w_i$ 为 $0$，表示这个敌人不需要 $La\_Pluma$ 费心， 同时也不能提高 $La\_Pluma$ 的注意， 若为 $1$， 表示将这个敌人分配给 $La\_Pluma$，最近博士的理智不太够用， 所以只需要输出**字典序最小**的 $w$

对于 $100\%$ 的数据，$0 \le n \le 10^5 $， $ 0 \le a_i < 10^9$，$ 0 < b_i < 10^9$ 对于 $10\%$ 的数据， 保证 $n \le 10$ 对于 $50\%$ 的数据， 时限为 $1s$ 对于 $50\%$ 的数据， 空限为 $512 MB$ 以上数据范围存在重叠 **注：部分测试点拥有特殊的时空限制**