# 用多个栈实现队列

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

存储控制器只有栈，却收到了一串队列操作。它提前知道全部操作，希望在规定时间交付元素，同时尽量减少栈操作次数。

(本故事由GPT-6重写)

## 形式化问题描述

有 $n$ 个初始为空的栈，需要实现初始为空的队列的 $m$ 次操作。字符串中的 `0` 表示队列入队，`1` 表示队列出队。出队应取出最早入队且尚未出队的元素；空队列上的出队操作无效。

第 $t$ 次队列操作对应时间段 $t$ .整个操作串提前给出，但入队元素只在其入队时间段可读，出队元素必须在对应的出队时间段输出。每个时间段可以执行以下操作任意非负整数次：

1. 将该时间段的输入元素压入一个栈，费用为一。
2. 将一个栈顶元素弹出并输出，费用为一。
3. 将一个栈顶元素弹出，再压入另一个栈，费用为二。

元素由这些栈保存。只要求这 $m$ 次队列操作的出队结果正确；不需要维护后续操作的状态。求最少的栈压入与弹出次数总和。输入只给出操作类型，不需要给出或输出元素的值。

## 输入格式

第一行两个整数 $n,m$ .第二行是长度为 $m$ 的 `0` / `1` 字符串。若 $m=0$ ，该行为空。

## 输出格式

输出一行一个整数，表示最小总费用。

## 样例

### 样例 1

### 输入

```text
2 10
0001110011
```

### 输出

```text
12
```

### 样例 2

### 输入

```text
2 0

```

### 输出

```text
0
```

### 样例 3

### 输入

```text
2 6
110010
```

### 输出

```text
2
```

## 样例解释

样例一最初三个元素中，有两个可以直接放在不同栈底，第三个需要转移一次，费用为八。后面两个元素各需一次压入和一次弹出，再花四次。样例二没有操作。样例三最初两次出队无效，两个入队元素中只有第一个会出队，只需存储并输出它，费用为二。

## 数据范围与保证

$2\le n\le10^9$ , $0\le m\le4\times10^6$ . 操作串只含 `0` 和 `1` .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |