E. Чихэр болон чулуунууд

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

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

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

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

Жаахан Жералд, түүний дасгалчуулагч Майк маш сонирхолтой тоглоом тоглодог. Тоглоомын эхлэлд $n$ ширхэг овоолгоостой чихэр, $m$ ширхэг овоолгоостой чулуунууд байгаа. Жералд болон Майк ээлжилж нүүх ба Майк түрүүлж эхэлнэ. Өөрийн нүүдлээр Майк хэдэн чихэр, чулуунуудыг Жералд идсэнийг тооцдог. Жералд $a$ ширхэг чихэр, $b$ ширхэг чулуунуудыг идсэн байг. Тэгвэл Майк Жералдыг $f(a, b)$ оноогоор шагнадаг. Жералд өөрийн нүүдлээр овоолгоостой чихэрээс нэгийг эсвэл овоолгоостой чулуунуудаас нэгийг иддэг. Жералдыг зөвхөн нэг чихэр, нэг чулуу үлдээсэн байгааг Майк харах үед тэрээр сүүлийн удаа оноогоор шагнаж тоглоом дуусдаг. Жералд чихэрүүдийг бүгдийг нь идэж болохгүй ба бүх чулуунуудыг мөн адил. Жералдад боломжит хамгийн өндөр оноог авахын тулд хэрхэн тоглохыг нь хэлж өг: боломжит хамгийн сайн тоглолтын стратегиудын нэгийг олох шаардлагатай.

Оролт

Эхний мөр $n, m, p (1 <= n, m <= 20000, 1 <= p <= 10^9)$ гурван бүхэл тоонуудыг агуулна. Хоёр дахь мөр $x_0, x_1, ..., x_{n - 1} (0 <= x_i <= 20000)$ гэсэн $n$ ширхэг бүхэл тоонуудыг агуулна. Гурав дахь мөр $y_0, y_1, ..., y_{m - 1} (0 <= y_i <= 20000)$ гэсэн $m$ ширхэг бүхэл тоонуудыг агуулна. $f(a, b)$-ийн утга нь $x_a + y_b$ нийлбэрийг $p$ тоонд хуваагаад гарсан үлдэгдэл юм.

Гаралт

Хамгийн эхний мөрөнд Жералд авч чадах хамгийн өндөг оноог зөвхөн хэвлэнэ. Хоёр дахь мөрөнд $n + m - 2$ ширхэг тэмдэгтүүдээс тогтох тэмдэгтэн цувааг хэвлэнэ. Цувааны тэмдэгт бүр "C" эсвэл "S" байх ба хэрэв $i$ дахь тэмдэгт "C" бол Жералд $i$ дахь нүүдэлд чихэр идсэн, хэрэв чулуу идсэн бол "S" байна.

Орчуулсан: devman

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

Оролт
2 2 10
0 0
0 1
Гаралт
2
SC
Оролт
3 3 10
0 2 0
0 0 2
Гаралт
10
CSSC
Оролт
3 3 2
0 1 1
1 1 0
Гаралт
4
SCSC

Тэмдэглэл

Эхний тестэд хэрэв Жералд анхны нүүдлээр чулуу идвэл нэг оноог, харин чихэр идвэл тэг оноог авна. Ямар ч тохиолдолд Жералд эхний нүүдлээс өмнө тэг оноог авч, хоёр дахь нүүдлийнхээ дараа 1 оноо авах болно. Тиймээс Жералдын авч чадах хамгийн их оноо нь 2 ба эхлээд чулуу идэн дараа нь чихэр идвэл уг оноог авч чадна.

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