B. Хямдралууд

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

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

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

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

Поликарпус нэг өдөр гэртээ харих замаараа супермаркетаар дайрчээ. Тэгэхэд дэлгүүр модон сандалдаа онцгой хямдрал зарласан байж гэнэ. Хямдрал нь: хэрэглэгчийн сагсанд дор хаяж нэг модон сандал байвал тэр сагсанд байгаа бараануудаас хамгийн хямд үнэтэй бараа нь $50\%$ хямдарна ($2$ дахин хямдарна гэсэн үг). Хэрэв хамгийн хямд үнэтэй бараа олон байвал хямдрал аль нэг бараанд л үйлчилнэ!

Поликарпуст $k$ тооны сагс байгаа ба тэр дэлгүүрээс бүх модон сандал, харандаануудыг худалдан авахыг хүсчээ. Бараануудын нийт үнийг байж болох хамгийн бага байхаар (хямдралыг оруулна) модон сандлууд болон харандаануудыг худалдааны сагснуудад хуваарилахад туслаарай.

Поликарпус бараануудыг худалдан авахдаа бүх $k$ сагснуудыг ашиглах ёстой ба ямар ч сагс хоосон байх ёсгүй. Худалдааны сагс бүр хэдэн ч модон сандал болон харандаа агуулж болно.

Оролт

Оролтын эхний мөр нь дэлгүүрт байгаа бараануудын тоо болон сагсны тоог харуулсан $n$ ба $k$ ($1 ≤ k ≤ n ≤ 10^{3}$) 2 бүхэл тоог агуулна. Дараагийн $n$ ширхэг мөрүүдэд барааг тодорхойлох "$c_{i}$ $t_{i}$" (хашилтгүйгээр) тоонууд өгөгдөнө. Энд, $c_{i}$ ($1 ≤ c_{i} ≤ 10^{9}$) бүхэл тоо нь $i$-р барааны үнэ, $t_{i}$ ($1 ≤ t_{i} ≤ 2$) бүхэл тоо нь $i$-р барааны төрөл ($1$ бол модон сандал, $2$ бол харандаа) байна. Нэг мөрөнд байгаа тоонууд хоосон зайгаар тусгаарлагдана.

Гаралт

Эхний мөрөнд хямдралыг багтаасан, бараануудын хамгийн бага нийт үнийг харуулах бодит тоог таслалаас хойш нэг оронгийн нарийвчлалтай хэвлээрэй.

Дараах $k$ мөрүүдэд сагсан дахь бараануудын тайлбарыг хэвлэ. $i$-р мөрөнд $i$-р сагсны тайлбар "$t$ $b_{1}$ $b_{2}$ $...$ $b_{t}$" (" тэмдэггүйгээр)-г хэвлээрэй. Энд, $t$ бол $i$-р сагсан дахь барааны тоо бөгөөд $b_{1}, b_{2}, ..., b_{t}$ ($1 ≤ b_{j} ≤ n$) дараалал нь сагснуудад хуваарилагдсан бараануудын дугаар байна. Бүх сагсан дахь хос бараануудын дугаар ялгаатай байх ба нэг бараа яг нэг л сагсанд орно. Та сагсан дахь бараанууд болон сагснуудыг ямар ч дарааллаар хэвлэж болно. Бараанууд нь оролтод өгсөн дарааллаараа, $1$-$n$ хүртэл тоогоор дугаарлагдана.

Хуваарилалт хийх боломж олон байвал аль нэгийг нь хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
3 2
2 1
3 2
3 1
Гаралт
5.5
2 1 2
1 3
Оролт
4 3
4 1
1 2
2 2
3 2
Гаралт
8.0
1 1
2 4 2
1 3

Тэмдэглэл

Эхний жишээнд, эхний сагс $1$ болон $2$ дахь барааг, $2$ дахь сагс $3$ дахь барааг агуулж болох юм. Энэ аргаар сагс бүрд модон сандал орон ба сагс бүр хямдхан бараандаа $50\%$-ийн хямдрал эдэлнэ. Бүх барааны нийт үнэ: $2 \cdot 0.5 + (3 + 3 \cdot 0.5) = 1 + 4.5 = 5.5$ болно.

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