G. Duas cargas na circular

Há $n$ depósitos em uma rota circular. O trecho $i$ liga o depósito $i$ ao próximo depósito no sentido horário; o próximo de $n$ é $1$. Para $n=2$, há dois trechos distintos entre os depósitos.

O depósito $i$ possui inicialmente $a_i$ caixas vermelhas e $b_i$ caixas azuis e deve terminar com $A_i$ caixas vermelhas e caixas azuis. Para cada cor, o total inicial é igual ao total desejado.

Um plano atribui a cada trecho dois inteiros $f_i$ e $g_i$, os fluxos líquidos de caixas vermelhas e azuis no sentido horário. Um valor negativo representa transporte no sentido anti-horário. Para cada depósito, devem valer $a_i+f_{i-1}-f_i=A_i,b_{}$ onde e .

O trecho $i$ admite no máximo $c_i$ caixas no total: $|f_i|+|g_i|\le c_i$. O custo do plano é . Não é necessário especificar uma ordem de envio: as equações e as capacidades definem completamente um plano válido.

Determine o menor custo de um plano válido, ou informe que não existe um.

3
2 0 0 0 2
0 0 0 1 2
0 1 2 0 2

3