대통령 선거

몇 주 뒤 마레시아에서 새 대통령을 뽑는다. 정당은 입헌당과 연방당 둘뿐이고, 각 당은 대통령 후보를 한 명씩 낸다. 이 두 사람 중 한 명이 새 대통령이 된다.

올해 당신은 그 어느 때보다 깊이 관여한다. 입헌당 후보가 바로 당신이기 때문이다. 선거가 몇 주 남지 않은 지금, 전국을 무작정 도는 대신 몇몇 주에 집중하기로 한다.

마레시아의 선거 제도는 꽤 복잡하다. 등록 유권자는 모두 두 후보 중 정확히 한 명에게 투표하지만, 표는 전국 단위로 합산하지 않는다. 대신 주마다 대의원 수가 정해져 있다. 주민 투표가 끝나면 모든 주의 대의원이 수도 애쉬윙턴까지 걸어와 마지막 투표를 한다. 대의원은 법에 따라 자기 주에서 더 많은 표를 얻은 후보에게 투표해야 한다.

선거 운동 팀이 주별 투표 성향을 정확하게 정리했다. 그래서 모든 주에 대해 다음 세 가지를 안다.

• 입헌당에 확실히 투표하는 유권자 수
• 연방당에 확실히 투표하는 유권자 수
• 아직 마음을 정하지 못한 유권자 수

앞의 두 부류는 더 이상 선거 운동에 흔들리지 않는다. 남은 몇 주 동안 설득할 대상은 세 번째 부류뿐이다. 승리를 확정하려면 최소 몇 명을 더 설득해야 하는지 구하라.

주 단위든 전국 단위든 동점이 나오면, 법에 따라 두 정당 중 더 오래된 연방당이 이긴다.

첫 줄에 주의 개수 $S$가 주어진다.

이어지는 $S$개의 줄에 네 정수 $D_i$, $C_i$, $F_i$, $U_i$가 주어진다.

• $D_i$는 $i$번째 주의 대의원 수이다.
• $C_i$는 $i$번째 주에서 입헌당에 확실히 투표하는 등록 유권자 수이다.
• $F_i$는 $i$번째 주에서 연방당에 확실히 투표하는 등록 유권자 수이다.
• $U_i$는 $i$번째 주에서 아직 마음을 정하지 못한 유권자 수이다.

대의원은 전부 합쳐 2016명 이하이고, 등록 유권자는 전부 합쳐 $10^9$명 이하이다. 모든 주에는 대의원이 한 명 이상 있고 등록 유권자도 한 명 이상 있다. 주는 하나 이상이다.

승리를 확정하기 위해 설득해야 하는 최소 유권자 수를 한 줄에 출력한다. 선거에서 이길 방법이 없으면 대신 impossible을 출력한다.