E. Хэммингийн гурвал

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

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

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

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

Бяцхан Крис хар дарж зүүдэлж байна. Тэр ч бүү хэл зүүдэндээ математикийн тухай бодож байна.

Крис $n$ урттай, индексүүд нь $1$-с $m$ хүртэл дугаарлагдсан $m$ хоёртын тэмдэгт мөрийн талаар зүүдэлж байв. Хамгийн аймшигтай хэсэг нь тэмдэгт мөр бүрийн битүүд өсөхөөр эсвэл буурах дарааллаар байрласан. Жишээлбэл, Крис дараах 5 уртай 4-н тэмдэгт мөрийг зүүдэлж байж болох юм:

$H(a, b)$ Хэммингийн зай гэдэг нь $n$ урттай $a$ ба $b$ хоёр тэмдэгт мөрийн хоорондох харгалзсан байрлалтай ялгаатай тэмдэгтүүдийн тоо юм.

Өөр өөр индекстэй гурван тэмдэгт мөр бүр нэг гурвалыг бүрдүүлдэг гэж Крис боддог. Хэрвээ $a$, $b$, $c$ гурвалын $H(a, b) + H(b, c) + H(c, a)$ нийлбэр бол зүүдэлсэн тэмдэгт мөрүүдээс бүтээгдсэн бүх тэмдэгт мөрийн гурвалаас хамгийн их тоог тоолвол тэр сэрж чадна.

Хар дарсан зүүднээсээ сэрэхэд нь Крисд тусал!

Оролт

Эхний мөрөнд $n$, $m$ ($1 ≤ n ≤ 10^{9}$; $3 ≤ m ≤ 10^{5}$) хоёр тоог зайгаар тусгаарлан оруулна, эдгээр нь урт болон тэмдэгт мөрийн тоо юм. Дараагийн $m$ мөр нь тэмдэгт мөрийг тодорхойлно. $i$-р мөр нь зайгаар тусгаарлагдсан $s_{i}$, $f_{i}$ ($0 ≤ s_{i} ≤ 1$; $1 ≤ f_{i} ≤ n$) хоёр бүхэл тоог агуулах ба $i$ индекстэй тэмдэгт мөрийг тодорхойлно; $i$-р тэмдэгт мөрийн эхний $f_{i}$ битүүд нь $s_{i}$-тэй тэнцүү, ба үлдсэн $n - f_{i}$ битүүд нь $1 - s_{i}$-тэй тэнцүү гэсэн утгатай. Крисийн зүүдэнд олон тэнцүү тэмдэгт мөр байж болно.

Гаралт

Нэг бүхэл тоо хэвлэнэ, гурвалын тэмдэгт мөрийн хоорондын Хэммингийн зайн нийлбэр хамгийн их байх өгөгдсөн тэмдэгт мөрийн гурвалын тоо байна.

Орчуулсан: Даариймаа

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

Оролт
5 4
0 3
0 5
1 4
1 5
Гаралт
3
Оролт
10 4
1 5
0 5
0 5
1 5
Гаралт
4
Сэтгэгдлүүдийг ачааллаж байна...