Cards (cards, 2s, 512M)

大象正在玩一个叫塔尖戮杀的游戏。他目前有 $n$ 张手牌，第 $i$ 张牌可以选择两种效果之一：加 $a_i$ 力量或完成一次伤害 $b_i$ 的攻击。大象一开始的力量是 $0$。如果你打出的手牌原始攻击为 $a$ 且当前有 $x$ 的力量，实际攻击伤害就会是 $a+x$。他总共打出的伤害是所有手牌卡牌造成的伤害之和。

他已经计划好了按什么顺序打这些牌，但是还没有想好每张牌触发哪个效果，于是他找到了你。请输出最优可以造成的伤害和任意一种方案。

输入格式

第一行一个正整数 $n$，表示手牌的数量。

接下来的 $n$ 行，每行包含两个非负整数 $a_i$ 及 $b_i$，描述每张牌的两种效果。

输出格式

第一行输出一个整数，表示最大可能的伤害和。

第二行输出 $n$ 个整数，表示对应手牌使用的效果，$1$ 表示选择加力量效果，$2$ 表示选择攻击效果。

如果有多种伤害最大的方案，输出任意一种。

样例输入1

4
5 1
4 1
2 3
15 1

样例输出1

22
1 1 2 2

一种最优策略为，对于第一张卡触发加力量效果，力量提升为 $5$；对于第二张卡触发加力量效果，力量提升为 $9$；对于第三张卡触发攻击，实际伤害为 $9+3=12$；对于第四张卡触发攻击，实际伤害为 $9+1=10$。总伤害 $22$。

样例输入2

3
1 10
10 100
100 1

样例输出2

111
2 2 2

一种最优策略为三张牌均触发攻击效果。

样例输入3、样例输出3

见选手文件夹下 ex_cards3.in 和 ex_cards3.ans。50。爆int。

样例输入4、样例输出4

见选手文件夹下 ex_cards4.in 和 ex_cards4.ans。5000。爆int。

数据范围

对于所有数据，$1\le n\le 5000$，$0\le a_i,b_i\le 10^9$。

对于 10% 的数据，$n\le 20$​。

对于 30% 的数据，$n\le 50$，$a_i,b_i\le 50$​。

对于 50% 的数据，$n\le 50$。

对于 70% 的数据，$n\le 400$。