Quadrat mínim P36417

Statement

thehtml

Teniu n rectangles de mida a × b que heu de guardar en un quadrat de mida m × 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 × 3 es poden guardar en un quadrat 8 × 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?

‍ ‍ ‍ (8,8) unit=0.6cm, linewidth=0.6 linecolor=black [fillstyle=crosshatch](-1,0)(-1,8)(7,8)(7,0) [fillcolor=cyan,fillstyle=solid](-1,0)(-1,2)(2,2)(2,0) [fillcolor=orange,fillstyle=solid](-1,2)(-1,4)(2,4)(2,2) [fillcolor=green,fillstyle=solid](0,4)(0,6)(3,6)(3,4) [fillcolor=red,fillstyle=solid](0,6)(0,8)(3,8)(3,6) [fillcolor=yellow,fillstyle=solid](3,0)(3,2)(6,2)(6,0) [fillcolor=blue,fillstyle=solid](4,2)(4,4)(7,4)(7,2) [fillcolor=pink,fillstyle=solid](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⁹.

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++