B. Шаасс ба Номын тавиур

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

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

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

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

Шаассад $n$ ном байдаг. Тэрээр өөрийн бүх номондоо зориулж байж болох хамгийн бага хэмжээтэй номын тавиур хийхийг хүсжээ. $i$-дах номны зузаан нь $t_i$ ба номын өргөн нь $w_i$ байна. Бүх ном ижил өндөртэй ба номын зузаан нь $1$ юм уу $2$ байна.

Шаасс номын тавиур дээр дараах байдлаар номоо өрнө. Эхлээд тэрээр хэсэг номыг сонгоод босоогоор нь өрнө. Дараа нь үлдсэн номнуудыг нь хөндлөнгөөр нь өмнөх номнуудын дээр нь тавина. Хөндлөнгөөр тавьсан номнуудын өргөний нийлбэр нь босоогоор өрөгдсөн номнуудын нийт зузаанаас их байж болохгүй. Жишээлбэл дараах хэлбэртэй байж болно.

Номнуудаа өрж болох хамгийн бага нийт зузааныг олоход нь Шаассд туслана уу.

Оролт

Эхний мөрөнд номын тоо болох $n$ ($1 ≤ n ≤ 100$), дараагийн $i$ дэх мөрөнд $t_i, w_i$ ($1 ≤ t_i ≤ 2$, $ 1 ≤ w_i ≤ 100$) байна.

Гаралт

Номнуудаа өрж болох хамгийн бага нийт зузааныг хэвлэ.

Орчуулсан: Говьхүү

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

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