E. Чихэрийн дэлгүүр

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

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

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

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

Алдарт Кодпорсын цэцэрлэг 1-ээс $n$-ээр дугаарлагдсан $n$ хүүхдүүдээс бүрдэнэ. Эцэг эхчүүд нь хүүхдүүддээ халаасны мөнгө рублээр өгдөг.

Өнөөдөр тэд тосгоны хамгийн том чихрийн дэлгүүрт очиж байгаа. Дэлгүүр чихрийг боодлоор зардаг: 1-ээс $m$-г оролцуулан хооронд байх $i$ бүрийн хувьд яг $i$ чихрийг агуулах боодлыг зардаг. Нэг чихэр нэг рубль болохоор $x$ чихэр агуулсан боодол $x$ рубль.

1-р хүүхдээс авхуулан хүүхдүүд ээлжээр чихрүүд худалдаж авна. Ээлж бүрд $i$ дахь хүүхэд нэг боодол чихэр худалдаж авна. Кодпорс цэцэрлэгийн маш өрсөлдөөнтэй байдлаас болж нэг ээлжид хүүхдийн худалдаж авсан боодол дахь чихрийн хэмжээ өмнөх ээлжид боодлыг худалдаж худалдаж авсан хүүхдийн чихрийн хэмжээнээс эрс их байна (эхний ээлжид хүүхэд ямар ч боодолтой чихэр худалдаж авч болно). Тэгээд ээлж $i + 1$ хүүхэдэд шилжиж эсвэл $n$ дахь хүүхдийн ээлж байсан бол 1-р хүүхдэд шилждэг. Энэ процесс ямар ч үед зогсож болох боловч худалдан авах процессийн төгсгөлд бүх хүүхдүүд адил тооны боодолтой байх ёстой. Мэдээж хүүхэд бүрийн чихэрд үрж байгаа мөнгөний хэмжээ халаасных нь мөнгийг давах ёсгүй.

Та чихрийн дэлгүүрт ажилдаг ба хүүхдүүдэд чихрийг нь бэлдэх гэж байгаа. Хүүхдүүдэд зарж болох хамгийн их чихрийн хэмжээг ол. Хэрэв хүүхдүүд ямар ч чихэр худалдаж авч чадахгүй (хагалттай халаасны мөнгөгүй) бол 0 хэвлэнэ.

Оролт

Эхний мөр харгалзан хүүхдийн тоо, чихрийн дэлгүүрийн боодолд зарах хамгийн их чихрийн хэмжээг заах, зайгаар тусгаарлагдан $n, m (2 <= n <= 2 * 10^5, 2 <= m <= 5*10^6)$ бүхэл тоог агуулна.

Дараагаар нь $n$ мөрийн мөр бүр нь хүүхдүүдийн халаасны мөнгийг заах $\frac{m * (m + 1)}{2}$-с хэтрэхгүй ганц бүхэл тоог агуулна. Халаасны мөнгө 1-р хүүхдээс $n$ хүүхэд хүртэлх даарааллаар өгөгдөнө.

C++ дээр 64-bit бүхэл тоог уншихдаа бүү %lld хэрэглэ. cin, cout урсгал эсвэл %I64d хэрэглэ.

Гаралт

Чихрийн дэлгүүрийн зарж чадах хамгийн их чихрийн хэмжээг дүрслэх ганц бүхэл тоог хэвлэнэ.

Орчуулсан: devman

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

Оролт
2 5
5
10
Гаралт
13
Оролт
3 8
8
16
13
Гаралт
32
Оролт
2 5000000
12500002500000
12500002500000
Гаралт
12500002500000

Тэмдэглэл

Эхний жишээнд 13 чихэр зарсан тохиолдол доорх байдлаар гарч ирсэн.

  • Ээлж 1. 1-р хүүхэд 1 чихэр худалдаж авсан.

  • Ээлж 2. 2-р хүүхэд 3 чихэр худалдаж авсан.

  • Ээлж 3. 1-р хүүхэд 4 чихэр худалдаж авсан.

  • Ээлж 4. 2-р хүүхэд 5 чихэр худалдаж авсан.

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