几周后，马雷西亚国将选出新总统。参加竞选的两个政党分别是公民党和联邦党，每个政党各有一位总统候选人。你是公民党的候选人，希望在剩下的几周里把精力集中到真正需要争取的州。

这个国家的选举制度较为复杂。每名登记选民都会投票给两位候选人中的一位，但选票不是直接在全国范围内累计。每个州拥有固定数量的代表。州内投票结束后，该州的全部代表都必须把票投给在本州获得严格多数选民支持的候选人。如果州内票数相同，则联邦党获胜。

竞选团队已经准确统计出每个州的三类选民：确定支持公民党的人、确定支持联邦党的人，以及尚未决定的人。前两类选民不会改变立场，你只能争取尚未决定的选民。获得严格超过全国代表总数一半的代表票才能成为总统；如果全国代表票相同，同样由联邦党获胜。

请计算为了确保公民党获胜，至少需要争取多少名尚未决定的选民。

输入格式

第一行包含一个整数 $S$，表示州的数量。

接下来 $S$ 行，第 $i$ 行包含四个整数 $D_i,C_i,F_i,U_i$：$D_i$ 表示该州的代表数，$C_i$ 表示确定支持公民党的选民数，$F_i$ 表示确定支持联邦党的选民数，$U_i$ 表示尚未决定的选民数。

输出格式

输出一个整数，表示为了确保获胜至少需要争取的选民数；如果无论如何都不能获胜，输出 impossible。

3
7 2401 3299 0
6 2401 2399 0
2 750 750 99

50

3
7 100 200 200
8 100 300 200
9 100 400 200

impossible

3
32 0 0 20
32 0 0 20
64 0 0 41

32

说明/提示

数据范围与约定

• 全国代表总数不超过 $2016$
• 全国登记选民总数不超过 $10^9$
• 每个州至少有一名代表和一名登记选民
• 至少有一个州
• 州级和全国级票数相同时均判联邦党获胜