### 问题描述 有 $n$ 个商店正在促销。在一个商店中，你可以选择不购买商品，或购买一件商品，或购买两件商品。在一个商店中，你最多购买一次。 对于第 $i$ 个商店，购买一件商品的花费为 $w_{i,1}$，购买两件商品的花费为 $w_{i,2}$。注意不保证 $w_{i,2}$ 大于 $w_{i,1}$，也不保证 $w_{i,2}$ 小于两倍的 $w_{i,1}$。 现在对于 $1$ 到 $2n$ 之间的每一个整数 $k$，你需要求出购买刚好 $k$ 个商品的花费总和的最小值。 ### 输入格式 输入第一行包含一个正整数 $n$，表示商店的总数。 接下来 $n$ 行，每行包含两个正整数 $w_{i,1}$，$w_{i,2}$，表示在第 $i$ 个商店购买一件商品和两件商品的花费。 ### 输出格式 输出 $2n$ 行，每行一个正整数，其中第 $i$ 行为刚好购买 $i$ 个商品的花费总和的最小值。 ### 样例输入 ```text 2 9 1000000000 1000000000 7 ``` ### 样例输出 ```text 9 7 16 1000000007 ``` ### 说明 当 $k$ 等于 $1$ 时，最优策略为在第一个商店购买一个商品，不在第二个商店购买商品。 当 $k$ 等于 $2$ 时，最优策略为不在第一个商店购买商品，在第二个商店购买两个商品。 当 $k$ 等于 $3$ 时，最优策略为在第一个商店购买一个商品，在第二个商店购买两个商品。 当 $k$ 等于 $4$ 时，最优策略为在第一个商店购买两个商品，在第二个商店购买两个商品。 ### 评测数据规模 对于 $20$% 的评测数据，$1\leq n \leq 10^3$。 对于 $100$% 的评测数据，$1\leq n \leq 10^5$，$1\leq w_{i,1},w_{i,2} \leq 10^9$。