Van N darab pálcánk, amelyek hossza S₁, S₂, ..., S_N. A pálcák összeilleszthetők: egy S_i és egy S_j hosszúságúból készíthetünk S_i+S_j hosszúságút. Szeretnénk a pálcákból egy szabályos háromszöget készíteni, amelynek oldala a lehető legnagyobb.

Írjunk programot, ami megadja, hogy mekkora a legnagyobb elkészíthető szabályos háromszög oldalhossza. Ha nem készíthető egyenlő oldalú háromszög a pálcákból, akkor 0-t kell kiírni. Nem kötelező az összes pálcát felhasználni.

A bemenet több tesztesetet tartalmaz. Minden eset két sorból áll: az első sor a pálcák DB darabszámát tartalmazza, a második pedig a pálcák H_i hosszát, szóközökkel elválasztva. ( 4 <= DB <= 100, 1<= H_i <= 100 )

Minden sorba egyetlen számot kell kiírni, az adott tesztesethez tartozó legnagyobb lehetséges oldalhossz értékét.

Bemenet	Kimenet
5 1 1 1 1 1 4 1 2 3 4 8 2 4 4 9 3 7 6 2 0	1 0 11

A feladat forrása: BME Challenge 24, 2011 EC

Algoritmusok: dinamikus programozás