E. Мэдээллийн шинэчлэл

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

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

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

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

Аль хэдийн XXI зуун болчихсон байхад Далайн морьнуудын хотод хэвлэл мэдээлэл тийм ч сайн хөгжөөгүй билээ. Хотууд зам дагуу явж мэдээ хүргэдэг мэдээ түгээгчээс л сонин содон мэдээ авдаг байлаа. Далайн морьдын хотын замын сүлжээ дурын нэг хотоос өөр нэг хот руу зөвхөн нэг замаар явж хүрэх боломжтой байхаар баригджээ. Бүх зам уртаараа өөр хоорондоо адил юм.

Хойд туйлын удирдлагууд мэдээллийн шинэчлэл хийх шийдвэр гаргажээ. Энэхүү шинэчлэлд хэд хэдэн хотуудыг хамруулахаар сонгоод, тэдгээрийг бүс нутгийн төв болгожээ. Тухайн бүс нутгийн төвийг барьж байгуулахын тулд жилд $k$ пишлар (тус хотын мөнгөн тэмдэгт) шаардлагатай юм. Бүс нутгийн төв нь үргэлж хамгийн сүүлийн үеийн мэдээлэлтэй байдаг гэж үздэг байв.

Бүс нутгийн төвөөс бусад газар тухайн газруудаа мэдээллээр хангаж байх үүрэгтэй төвүүдийг томилон ажиллуулах шийдвэр гаргав. Энэ тохиолдолд бүтээн байгуулалтын ажилд жилд $d_{len}$ пишлар шаардлагатай ба үүнээс $len$ пишларыг тухайн хотоос харгалзах бүсийн төв рүү хүрэх зайд бий болгох замнуудыг барьж байгуулахад хэрэглэнэ.

Энэхүү шинэчлэлийг хийхэд хамгийн багадаа хичнээн хэмжээний зардлаар хийж болох утгыг ол.

Оролт

Хамгийн эхний мөр $n$ болон $k$ ($1 ≤ n ≤ 180, 1 ≤ k ≤ 10^{5}$) гэсэн хоёр тоог агуулж байна. Хоёр дахь мөр нь $1$ ($d_{i} ≤ d_{i + 1}, 0 ≤ d_{i} ≤ 10^{5}$) - ээс дугаарлаж эхлэх $n - 1$ ширхэг $d_{i}$ гэсэн бүхэл тоонуудыг агуулж байна.

Дараагийн $n - 1$ гэсэн мөрнүүд нь нэг замаар холбогдсон хоёр хотыг харуулж байна.

Гаралт

Эхний мөрөнд тухайн бүтээн байгуулалтыг хийхэд нэг жилд хамгийн багадаа хичнээн пишлар шаардлагатай болохыг тооцож гарга. Хоёр дахь мөрөнд $i$ дахь хотод хамаарах бүс нутгийн төвийн тоог харуулах $n$ гэсэн тоонууд гарга.

Хэрэв хэд хэдэн зөв хариу гарвал аль нэгийг сонго.

Орчуулсан: Энхгэрэл

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

Оролт
8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5
Гаралт
38
3 3 3 4 3 4 3 3 
Сэтгэгдлүүдийг ачааллаж байна...