eolymp
bolt
Try our new interface for solving problems
Məsələlər

Нам нужно больше менеджеров!

Нам нужно больше менеджеров!

Zaman məhdudiyyəti 15 saniyə
Yaddaşı istafadə məhdudiyyəti 512 MiB

Медиакомпания, в которой Вы работаете, намерена заменить свою организационную структуру (без начальников) на иерархическую. Будет выбран генеральный директор, которому будут отчитываться все остальные - прямо или косвенно. У каждого другого сотрудника будет ровно один непосредственный руководитель. Поскольку такая реформа неизбежно приведет к возникновению трений между работниками, цель вашей компании - выбрать иерархию, минимизирующую социальные издержки для фирмы.

Количество разногласий между двумя коллегами, вынужденных вступать в отношения начальник - подчиненный, пропорционально количеству политических вопросов, по которым они не согласны. В вашей компании каждый сотрудник имеет очень решительные взгляды на каждую из n наиболее распространенных политических тем: в каждой из n категорий мнения сотрудника могут быть как левыми, так и правыми. Что еще хуже, нет двух сотрудников, имеющих одинаковые убеждения. Стоимость непосредственного подчинения одного сотрудника другому равна количеству тем, по которым они не согласны. Стоимость новой организационной структуры равна сумме затрат на трение между каждыми двумя сотрудниками, где один напрямую управляется другим. Вас просят рассчитать минимально возможную стоимость новой структуры.

Giriş verilənləri

Первая строка содержит количество тестов z (1z10). Далее следует описание тестов.

Каждый тест начинается двумя целыми числами n и m (1n20, 1m2^n) - количество тем, по которым работники имеют мнение, и количество работников. Каждая из следующих m строк содержит политические взгляды одного работника. Описание взглядов рабочего представляет собой строку, состоящую из n букв. Если i - ым является символ L (R), то работник имеет левый (правый) взгляд на i - ую тему.

Çıxış verilənləri

Для каждого теста выведите строку, содержащую одно число - минимальную стоимость иерархии управления.

Nümunə

Giriş verilənləri #1
1
5 4
LLLLL
LLLLR
RRRRL
RRRRR
Çıxış verilənləri #1
6
Mənbə 2018 Петрозаводск, Зима, Jagiellonian U, Январь 30, Задача G