B. Мишка ба аялал

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

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

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

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

Бяцхан Мишка гайхалтай аялагч ба маш олон улсаар аялсан. Энэ удаад хаашаа аялахаа бодсоны эцэст тэр үзэсгэлэнт XXX буюу хойд зүгийн төдийлэн нэрд гараагүй улсыг сонгосон.

XXX-н тухай зарим сонирхолтой баримтууд байна:

  1. XXX нь $n$ хотоос бүрдэх ба тэдгээрийн $k$ нь нийслэл хотууд.
  2. Хотын бүх хот үзэсгэлэнтэй боловч тус бүрдээ өөрийн үзэсгэлэнтэй. $i$-р хот $c_{i}$ үзэсгэлэнтэй.
  3. $1$ болон $n$ дугаартай хотуудыг оруулаад бүх хотууд дарааллаад замуудаар холбогдсон, $1 -- 2 -- ... -- n -- 1$ цикл бүхий зам үүсгэнэ. Тодорхой хэлбэл $1 ≤ i < n$ бүрийн хувьд $i$ болон $i + 1$ хотуудыг холбосон зам бий, мөн $1$ болон $n$-р хотыг холбосон зам бий.
  4. Нийслэл хот бүр бусад хотуудтай шууд холбогдсон замтай. Тодорхой хэлбэл хэрвээ $x$ хот нь нийслэл хот бол $1 ≤ i ≤ n,  i ≠ x$ бүрийн хувьд $x$ болон $i$ хотуудыг холбосон зам байна.
  5. Дурын хоёр хотын хооронд хамгийн ихдээ нэг зам байна.
  6. Замыг туулах өртөг нь түүний холбосон хотуудын үзэсгэлэнгээс хамаарна. Хэрвээ $i$ ба $j$ хотуудыг холбосон зам байвал үүнийг туулах өртөг нь $c_{i}*c_{j}$ байна.

Мишка аялалд зориулж эд зүйлсээ цуглуулж эхэлсэн боловч ямар маршрутаар явахаа шийдээгүй байна тиймээс тэр таныг XXX дахь зам бүрийг туулах зардлын хураангуйг тодорхойлж өгнө үү гэж хүсч байна. Тодорхой хэлбэл $a$ ба $b$ хоёрын хооронд зам байх $a$ ба $b$ ($a < b$) хос хот бүрийн хувьд та $c_{a}*c_{b}$ үржвэрүүдийн нийлбэрийг олно. Та түүнд туслах уу?

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($3 ≤ n ≤ 100 000, 1 ≤ k ≤ n$) байх ба XXX дахь хотууд болон нийслэл хотуудын тоо юм.

Оролтын хоёр дахь мөрөнд $n$ бүхэл тоон утга $c_{1}, c_{2}, ..., c_{n}$ ($1 ≤ c_{i} ≤ 10 000$) байх буюу хотуудын үзэсгэлэн юм.

Оролтын гурав дахь мөрөнд ялгаатай $k$ бүхэл тоо $id_{1}, id_{2}, ..., id_{k}$ ($1 ≤ id_{i} ≤ n$) байх буюу нийслэл хотуудын дугаар юм. Дугааруудыг өсөх дарааллаар өгнө.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 1
2 3 1 2
3
Гаралт
17
Оролт
5 2
3 5 2 2 4
1 4
Гаралт
71

Тэмдэглэл

Доорх зураг эхний жишээг тодорхойлно:

Нийт нийлбэр $17$-той тэнцүүг эндээс харахад хялбар байна.

Доорх зураг хоёрдугаар жишээг тодорхойлно:

Нийт нийлбэр нь $71$-тэй тэнцүүг эндээс харахад хялбар байна.

Сэтгэгдлүүдийг ачааллаж байна...