记程序结束前 p 数组元素的最大值为 P，则该代码的时间复杂度是（）。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long

int n, m;
std::vector<int> k, p;

inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = x * x)
        if (k & 1) ans = ans * x;
    return ans;
}

std::vector<int> ansl, ans2;
int cnt1 = 0, cnt2 = 0;

inline void dfs(std::vector<int>& ans, int& cnt,
                int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i)
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
}

int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &k[i], &p[i]);

    dfs(ansl, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);

    std::sort(ansl.begin(), ansl.end());
    int newcnt1 = 1;
    std::vector<int> cntans1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i)
        if (ansl[i] == ansl[newcnt1 - 1]) {
            ++cntans1[newcnt1 - 1];
        } else {
            ansl[newcnt1++] = ansl[i];
            cntans1.push_back(1);
        }
    cnt1 = newcnt1;

    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 - 1; i >= 0; --i) {
        for (; las < cnt1 && ansl[las] + ans2[i] < 0; ++las) {}
        if (las < cnt1 && ansl[las] + ans2[i] == 0)
            ans += cntans1[las];
    }

    printf("%lld\n", ans);
    return 0;
}