Uzb Eng

C14C. Free Market
: 2 c
: 64

Abdullajon Free Market deb nomlangan dokonda harid qilishni yaxshi koradi. Chunki u yerda savdo pul bilan emas balki ayirboshlash ham mumkin. Abdullajon dokondagi buyumalar narxini biladi. Abdullajonning buyum almashtirish quyidagicha amalgi oshiradi:
d+s(x)>=s(y)
Bu yerda d Abdullajonning vijdon chegarasi, s(x) Abdullada almashtirmoqchi bolgan buyumlar narxlari yigindisi, s(y) Abdullajonning sotib olmoqchi bolgan buyumining narxi. Yani Abdullajon d+s(x) dan qimat buyumni olishga vijdoni yol qoymaydi! Dokonning shartlaridan bir shundaki dokonda bir kunda faqat bir marta ayir boshlashni amalgi oshirish mumkin. Birinchi kun Abdullajonda hech qanday buyum yoq. Abdullajonning iloji boricha ozida bor buyumlar narxilari yigindisi katta bolishi kerak. U iloji boricha tezroq yigishni xoxlaydi. Abdullajonga buyumlarning narxlar yigidisi eng katta narxni va bu buyumlarni yigishga ketadigan eng kam kunni toping.

:
Birinchi satrda n (1<= n <=50) va (1<= d <=10 4). Ikkinchi satrda n ta ci buyumlarning narxlari kiritiladi. (1<=ci<=104)

:
Abdulla yiga oladigan buyumlar narxi va buni yigish uchun kerak boladigan kunning minimalini toping.

3 2
1 3 10
3 5
1 2 3
10 10000
10000 9999 1 10000 10000 10000 1 2 3 4
4 3

6 2

50010 6
:
: Abdulla & Farziddin


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.