Quadrat mínim P36417

Statement

0.65 Teniu $n$ rectangles de mida $a \times b$ que heu de guardar en un quadrat de mida $m \times m$ . Tant els rectangles com el quadrat han d’estar aliniats amb l’eix horitzontal. Els rectangles no es poden girar, no es poden solapar, i no poden sortir fora del quadrat.

Per exemple, com es mostra a la dreta, 7 rectangles $2 \times 3$ es poden guardar en un quadrat $8 \times 8$ . És impossible guardar aquests rectangles en un quadrat més petit.

Donades $n$ , $a$ i $b$ , quina és la mínima $m$ que permet guardar els $n$ rectangles?

0.35

(8,8) (-1,0)(-1,8)(7,8)(7,0) (-1,0)(-1,2)(2,2)(2,0) (-1,2)(-1,4)(2,4)(2,2) (0,4)(0,6)(3,6)(3,4) (0,6)(0,8)(3,8)(3,6) (3,0)(3,2)(6,2)(6,0) (4,2)(4,4)(7,4)(7,2) (3,4)(3,6)(6,6)(6,4)

Entrada

L’entrada consisteix en diversos casos, cadascun amb tres enters $n$ , $a$ i $b$ , tots entre 1 i $10^9$ .

Sortida

Per a cada cas, escriviu la mínima $m$ que permet guardar tots els rectangles.

Public test cases

Input

7 2 3
12 2 3
13 2 3
15 2 3
16 2 3
24 2 3
1 5 5
1 321 1
990 42 23
1000000000 1000000000 1000000000

Output

8
9
10
10
12
12
5
321
1008
31623000000000

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++