B. Захиалгын ном

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

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

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

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

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

Захиалга гэдэг нь хөрөнгийн бирж дээр оролцогч хэн нэгэн үнэт цаас зарах эсвэл худалдаж авах заавар юм. $i$ захиалга нь $p_{i}$ үнэтэй ба $d_{i}$ чиглэл -- худалдаж авах эсвэл, зарах ба бүхэл тоон утга $q_{i}$. Энэ нь оролцогч үнэт цаас нэг бүрийг $p_{i}$ үнээр нийт $q_{i}$ ширхэгийг худалдаж авах эсвэл зарахад бэлэн гэсэн үг. $q_{i}$- мөн захиалгын хэмжээ гэж болно.

Ижил $p$ үнэтэй $d$ чиглэлтэй бүх захиалгууд нэг нийлмэл $p$ үнэтэй $d$ чиглэлтэй нэг захиалгад нэгтгэгдэнэ. Ийм захиалгын хэмжээ нь анхны захиалгуудын хэмжээнүүдийн нийлбэр байна.

Захиалгын ном бол эхний хэсэг нь зарах захиалгуудыг үнийн хувьд буурах дарааллаар агуулсан ба хоёр дахь хэсэг нь худалдаж авах захиалгуудыг үнийн хувьд буурах дарааллаар агуулсан нэгтгэгдсэн захиалгуудын жагсаалт юм.

$s$ гүнтэй захиалгын ном нь чиглэл бүртээ $s$ ширхэг шилдэг захиалгатай байна. Хэрвээ худалдаж авах захиалга нь худалдах захиалгаас их үнэтэй байвал худалдаж авах захиалга нь шилдэг гэсэн үг. Аль нэг чиглэлд $s$ нэгтгэгдсэн захиалга байвал эдгээр захиалгууд нь бүгдээрээ эцсийн захиалгын номонд байх болно.

Танд $n$ үнэт цаас солилцооны захиалга өгөгдсөн. Таны ажил бол эдгээр захиалгын хувьд $s$ гүнтэй захиалгын номыг хэвлэх.

Оролт

Оролт нь хоёр эерэг бүхэл тоо $n$ ба $s$ ($1 ≤ n ≤ 1000, 1 ≤ s ≤ 50$)-ээр эхлэх ба захиалгын тоо болон номны гүн.

Дараагийн $n$ мөрөнд $d_{i}$ ('$B$' эсвэл '$S$') үсэг болон бүхэл тоон утга $p_{i}$ ($0 ≤ p_{i} ≤ 10^{5}$) мөн бүхэл тоон утга $q_{i}$ ($1 ≤ q_{i} ≤ 10^{4}$) байх ба харгалзан чиглэл, үнэ болон хэмжээ байна. "$B$" үсэг нь худалдаж авахыг "$S$" нь зарахыг илтгэнэ. Ямар ч худалдаж авах захиалгын үнэ нь ямар ч зарах захиалгын үнээс их байна.

Гаралт

$s$ гүнтэй нэтгэгдсэн захиалгын номоос $2s$-ээс ихгүй мөрийг хэвлэ. Гаралтын захиалгын формат нь оролтынхтой адилхан байна.

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

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

Оролт
6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10
Гаралт
S 50 8
S 40 1
B 25 10
B 20 4

Тэмдэглэл

$x$ үнэтэй $y$ хэмжээтэй захиалгыг $(x, y)$ гэж тэмдэглэе. Жишээн дээр 3 нэгтгэсэн худалдаж авах захиалга (10, 3), (20, 4), (25, 10) байгаа ба хоёр зарах захиалга (50, 8), (40, 1) байна.

Та чиглэл бүрийн хувьд хоёроос ихгүй шилдэг захиалгыг хэвлэх хэрэгтэй ба худалдаж авах захиалгуудын хамгийн муу захиалга болох (10, 3)-г хэвлэхгүй.

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