E. Greedy задаргаа

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Билл амьдралын өөр хэсэгтээ greedy алгоритм хэрэглэхээр судалж байна. Одоогоор тэр мөнгө задлахад greedy алгоритм хэрэглэхээр судалж байна. Танд $n$ ширхэг ялгаатай үнэ бүхий хязгааргүй тооны зоос байгаа. Бидний даалгавар бол $x$ мөнгөн дүнг хамгийн цөөн зоосоор задлах юм. Greedy алгоритм алхам бүр дээрээ $x$-с хэтрэхгүй дүнтэй хамгийн том зоосыг авдаг. Мэдээж $1$ үнэтэй зоос байх л юм бол ямар ч $x$-г энэ алгоритмаар задалж болох билээ. Мэдээж энэ алгоритм ямар нэг задаргаа олсон ч энэ хамгийн цөөн зоос ашигласан байх албагүй юм. Жишээ нь $6$ дүнг ${1,3,4}$ зоосоор задлах үед алгоритм $4+1+1$ хариу гаргах ч хамгийн сайн шийдэл нь $1$-р цөөн зоос ашиглаж $3+3$ гэж задлах юм.

Иймд хэрвээ өгөгдсөн зооснуудаар дээрх greedy алгоритм хамгийн цөөн зоос ашигласан задаргаа хийж чадахгүй ямар нэг мөнгөн дүн байх бол тийм хамгийн бага мөнгөн дүнг ол.

Оролт

Эхний мөр зоосны тоо $n$ ($1 ≤ n ≤ 400$) өгөгдөнө. Дараагийн мөрөнд зоосны дүнг илэрхийлэх $a_i$ ($1 ≤ a_i ≤ 10^9$) гэх $n$ тоо өгөгдөнө. Энд $a_1 > a_2 > ... > a_n$ ба $a_n = 1$ байна.

Гаралт

Хэрвээ дээрх грийдий алгоритм ямар ч мөнгөн дүнг зөв задлах бол $-1$-г хэвлэ. Бусад тохиолдолд буруу задлах хамгийн бага мөнгөн дүнг хэвлэнэ.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
5
25 10 5 2 1
Гаралт
-1
Оролт
3
4 3 1
Гаралт
6
Сэтгэгдлүүдийг ачааллаж байна...