最近,我开始玩集换式卡牌游戏《Wizardry – The Meeting》。由于我非常想组建一套强力的卡组,我决定只在网上搜索最好的卡牌。事实证明,大多数卡牌都非常昂贵,只能靠极好的运气在购买随机卡包时获得,或者通过在线拍卖竞拍得到。由于拍卖非常耗时,而我更想把时间花在玩游戏上,而不是整天盯着拍卖,于是我产生了一个新想法:建立一个交易卡牌市场。
每种卡牌都是批量生产的,因此买家并不关心他们从哪个卖家那里购买特定的卡牌。因此,我的想法是为每种卡牌创建一个网页,用户可以在上面发布买入和卖出报价。以“Green Mana”卡牌为例:如果你想买一张,你可以创建一个买入报价,例如 $10.00$。这个报价意味着你愿意以 $10.00$ 或更低的价格购买该卡牌(如果有卖家愿意以更低的价格出售)。另一方面,如果你想卖出一张“Green Mana”卡牌,你可以创建一个卖出报价,例如 $12.01$。这个报价意味着你愿意以 $12.01$ 或更高的价格出售你的卡牌(如果有买家愿意以更高的价格购买)。
现在,网站每隔几秒钟就会根据这两种报价自动计算出一个卡牌价格。然后,它只考虑那些与该价格兼容的报价(如上所述),并尽可能多地满足这些报价。
作为一名有抱负的企业家,我决定我应该从网站上发生的每一笔交易中抽取佣金。但我遇到了一个小麻烦,即如何设计一种算法来确定价格,使得成交额(即价格乘以成功交易的数量)尽可能高(这意味着我的佣金也会尽可能高)。
输入格式
输入包含: 一行一个整数 $n$ ($1 \le n \le 10^5$),表示存在报价的不同价格数量。 $n$ 行,每行包含一个实数 $p$ 和两个整数 $b$ 和 $s$ ($0 < p \le 10^4, 0 \le b, s \le 10^6$),分别表示报价的价格(精确到小数点后两位)、该价格下的买入报价数量以及该价格下的卖出报价数量。
保证输入中的每个价格至少有一个买入或卖出报价,且没有价格重复出现。
输出格式
如果不存在任何价格能促成至少一笔交易,输出 “impossible”。否则,输出能产生最高成交额的价格以及该成交额。如果存在多个这样的价格,输出其中任意一个。两个数字均需输出,且精确到小数点后两位。
样例
样例输入 1
5 12.00 0 3 11.99 2 0 11.98 5 0 10.00 1 0 12.01 0 6
样例输出 1
impossible
样例输入 2
6 2.85 14 0 4.50 0 1 5.26 3 3 6.17 1 0 14.78 0 2 21.04 1 0
样例输出 2
5.26 21.04
样例输入 3
6 2.85 14 0 4.50 0 1 5.26 2 3 14.78 0 2 1.83 0 1 21.04 1 0
样例输出 3
21.04 21.04
说明
在第二个样例中,最优卡牌价格为 $5.26$,因为它产生了 $21.04$ 的最高可能成交额,共发生了四笔交易。总共有五位买家愿意支付至少 $5.26$:三位愿意支付正好 $5.26$,一位愿意支付 $6.17$,还有一位甚至愿意支付 $21.04$。另一方面,只有四位卖家愿意以 $5.26$ 的价格出售他们的卡牌:三位正好在这个价格,还有一位愿意以 $4.50$ 的价格出售。
注意,存在另一种解法:当卡牌价格为 $21.04$ 时,恰好会发生一笔交易,产生的成交额与上述最优成交额相同。