D. Сиел ба халз тулаан

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

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

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

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

Сиел, Жиро хоёр хөзрөөр тоглож байв. Жиро $n$ ширхэг хөзөртэй ба хөзөр болгон нь дараах хоёр чанартай. Үүнд байрлал (довтлох эсвэл хамгаалах) болон хүч багтана. Сиел $m$ хөзөртэй ба мөн адил дээрх хоёр чанартай болно. Мөн Сиелийн бүх хөзөрний байрлал нь довтлох гэдэг нь мэдэгдэж байгаа.

Одоо Сиел тулааны төлөвт байгаа бөгөөд Сиел дараах үйлдлүүдийг олон дахин хийж болно.Үүнд:

  1. Өмнө нь сонгогдоогүй $X$ хөзрийг сонгоно.
  2. Хэрэв Жиро энэ мөчид ямар ч амьд хөзөргүй байгаа бол тэрээр $X$-ын хүчтэй тэнцүү хэмжээний хохирол амсах юм. Эсрэг тохиолдолд Сиел Жирогийн аль нэг амьд $Y$ хөзрийг сонгох ба дараа нь:

    • Хэрэв $Y$-ын байрлал "довтлох" байгаад ($X$-н хүч $ ≥ $ $Y$-н хүч) гэсэн нөхцөл биелэж байвал Сиел довтолж $Y$ хөзөр үхэж Жиро ($X$-н хүч $-$ $Y$-н хүч)-тэй тэнцүү хэмжээний хохирол амсана.
    • Хэрэв $Y$-ын байрлал "хамгаалах" байгаад ($X$-н хүч $ > $ $Y$-ын хүч) нөхцөл биелэж байвал Сиел довтлоход $Y$ хөзөр үхэх боловч Жиро ямар ч хохирол амсахгүй.

Сиел өөрийн тулаанаа ямар ч үед дуусгаж болно. Тиймээс тэрээр бүх хөзрөө ашиглахгүй байж болох юм. Тэгвэл Сиелд тусалж Жирод учруулж болох нийт хохирлын хамгийн их хэмжээг тооцоолж өгнө үү.

Оролт

Эхний мөрөнд Жиро болон Сиелд байгаа хөзрийн тоо болох $n$, $m$ ($1 ≤ n, m ≤ 100$) бүхэл тоо өгөгдөнө.

Дараачийн $n$ мөрөнд мөр болгонд тэмдэгтээр илэрхийлэгдсэн $байрлал$ болон бүхэл тоогоор илэрхийлэгдсэн $хүч$ $(0 ≤ хүч ≤ 8000)$ байх ба эдгээр нь Жирогийн одоогийн хөзрүүдийн байрлал болон хүч юм. Байрлал нь "ATK" бол довтлох "DEF" бол хамгаалах байх юм.

Дараачийн $m$ мөрөнд мөр болгонд бүхэл тоогоор илэрхийлэгдсэн $хүч$ $(0 ≤ хүч ≤ 8000)$ байх ба эдгээр нь Сиелын одоогийн хөзрүүдийн хүч юм.

Гаралт

Гаралтанд ганц бүхэл тоо байх ба Жирод учруулж болох хохирлын хамгийн их хэмжээг хэвлэнэ.

Орчуулсан: Баатархүү

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

Оролт
2 3
ATK 2000
DEF 1700
2500
2500
2500
Гаралт
3000
Оролт
3 4
ATK 10
ATK 100
ATK 1000
1
11
101
1001
Гаралт
992
Оролт
2 4
DEF 0
ATK 0
0
0
1
1
Гаралт
1

Тэмдэглэл

Эхний жишээнд Сиел ижил хүч бүхий $3$-н хөзөртэй байх ба хамгийн зөв стратеги нь дараах хэлбэртэй байна. Эхлээд тэрээр эдгээр $3$-н хөзөрний аль нэгийг хэрэглэн "ATK 2000"-тай хөзөр лүү эхлээд довтлон тус хөзрийг устган Жирод $2500 - 2000 = 500$-ын хохирол учруулна. Дараа нь тэрээр $2$-дах хөзрөө ашиглан "DEF 1700"-тай хөзрийг устгана. Одоо Жиро ямар ч хөзөргүй болох ба Сиел $3$-дахь хөзрөө ашиглан Жиро руу довтлож $2500$-ын хохирол учруулах ба нийтдээ $500 + 2500 = 3000$-ын хохирол учруулах юм.

Хоёр дахь жишээнд тэрээр "1001"-тэй хөзрийг ашиглан "ATK 100"-руу довтлоно. Дараа нь "101"-тэй хөзрийг ашиглан "ATK 10"-руу довтлох ба одоо Сиел хэдий дахиад хөзөртэй байгаа хэдий ч тэр тулаанаа дуусгах ба ингэснээр нийтдээ $(1001 - 100) + (101 - 10) = 992$ хэмжээний хохирол учруулах юм.

Гурав дахь жишээнд тэрээр "ATK 0"-ыг хүч нь $0$-тэй тэнцүү хөзрөөр устгаж чадах боловч тус хөзрөөр "DEF 0"-тэй хөзрийг устгаж чадахгүй юм.

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