35285번 - 별동대 스페셜 저지

ibasic은 소규모 별동대를 운영하고 있는 지휘관이다. ibasic은 효과적인 병력 운용을 위해 별동대를 A 지역에 배치되는 대원 그룹과 B 지역에 배치되는 대원 그룹으로 나누기로 결정했다.

효과적으로 그룹을 구성하기 위해 ibasic은 대원의 능력을 분석했다. 대원을 $1$번부터 $N$번까지의 번호를 통해 구분할 때, $i$번 대원의 전투력은 A 지역에 배치될 때 $A_i$, B 지역에 배치될 때 $B_i$로 조사되었다. 또한, $i$번 대원의 협동심은 $S_i$로 조사되었다.

그룹의 전투력은 그룹에 속한 각 대원의 전투력의 합에 그룹의 협동력을 합한 값으로 정의된다. 그룹의 협동력은 모든 두 대원 쌍의 협동심의 곱을 합한 값이다. 그룹의 구성원이 한 명 이하일 경우 그룹의 협동력은 $0$이다.

별동대의 전투력은 두 그룹의 전투력의 합이다. 즉, A 지역에 배치된 대원의 집합을 $X$, B 지역에 배치된 대원의 집합을 $Y$라고 할 때 별동대의 전투력은 다음과 같다.

$$\sum_{i\in X}{A_i} + \sum_{i\in Y}{B_i} + \sum_{\substack{i, j\in X\\i<j}}{S_i S_j} + \sum_{\substack{i, j\in Y\\i<j}}{S_i S_j}$$

당신은 적절히 그룹을 나누어 별동대의 전투력을 최대화해야 한다. 별동대의 모든 병력을 사용하여 구성해야 하며, 빈 그룹이 있어도 무방하다.

첫 번째 줄에 정수 $N$이 주어진다. ($1\le N \le 40$)

두 번째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에 세 정수 $A_i$, $B_i$, $S_i$가 공백으로 구분되어 주어진다. ($\lvert A_i\rvert \le 10^{15}$; $\lvert B_i\rvert \le 10^{15}$; $\lvert S_i\rvert \le 10^7$)

첫 번째 줄에 별동대의 전투력과 전투력이 최대가 되는 분배의 가짓수를 공백으로 구분하여 출력한다.

두 번째 줄에 A 지역에 배치되는 대원 수와 B 지역에 배치되는 대원 수를 공백으로 구분하여 출력한다.

세 번째 줄에 A 지역에 배치되는 대원을 오름차순으로 공백으로 구분하여 출력한다. 단, A 지역에 아무도 배치하지 않는다면 0을 대신 출력한다.

네 번째 줄에 B 지역에 배치되는 대원을 오름차순으로 공백으로 구분하여 출력한다. 단, B 지역에 아무도 배치하지 않는다면 0을 대신 출력한다.

별동대의 전투력이 최대가 되는 분배가 여러 가지라면 그중 아무거나 출력한다.