暴力模拟,每次先往小的那一边递归,最优性剪枝。复杂度感觉不对,但是跑得飞快。
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
const int N = 100005;
int n, p, q, a[N], b[N];
LL ans = LLONG_MAX;
void solve(int l, int r, LL cur)
{
if (cur >= ans) return;
if (l > r) return MIN(ans, cur), void();
int mid = l;
F(i, l, r) if (a[i] < b[i]) swap(a[i], a[mid]), swap(b[i], b[mid++]);
if (mid - l > r - mid + 1)
{
F(i, mid, r) swap(a[i], b[i]), b[i] -= a[i];
F(i, mid, r) if (b[i] == 0) swap(a[i], a[r]), swap(b[i], b[r--]);
solve(mid, r, cur + p + q);
F(i, l, mid - 1) b[i] -= a[i];
solve(l, mid - 1, cur + p);
}
else
{
F(i, l, mid - 1) b[i] -= a[i];
solve(l, mid - 1, cur + p);
F(i, mid, r) swap(a[i], b[i]), b[i] -= a[i];
F(i, mid, r) if (b[i] == 0) swap(a[i], a[r]), swap(b[i], b[r--]);
solve(mid, r, cur + p + q);
}
}
signed main(void)
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >> n >> p >> q;
F(i, 1, n) cin >> a[i] >> b[i];
solve(1, n, 0);
cout << ans << '\n';
return 0;
}