保底：不管题目多难，20-60分的暴力/特殊性质分必须像吃饭一样自然拿下（不挂分）。 刺顶：在保底的基础上，利用剩余时间冲击1-2道题的满分正解。 班级口号/文化：“一分不丢是赢家，死磕正解易翻车”、“写暴力是为了保护正解”。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int n;
long long m;
long long x[MAXN], y[MAXN];

/* =========================================================
   【防线 1】极限暴力 (对应 N<=10, M<=20) -> 稳拿 25 分
   不带脑子的 DFS，穷举每种糖果买几颗
========================================================= */
namespace Subtask_DFS {
    long long max_candies = 0;

    // 当前在考虑第 type 种糖，手里还剩 money_left，已经买了 candies 颗
    void dfs(int type, long long money_left, long long candies) {
        max_candies = max(max_candies, candies);
        if (type > n) return;

        // 分支 1：这种糖果一颗都不买
        dfs(type + 1, money_left, candies);

        // 分支 2：这种糖果买 k 颗 (k > 0)
        long long current_cost = 0;
        for (long long k = 1; ; k++) {
            // 奇数颗加 x，偶数颗加 y
            if (k % 2 != 0) current_cost += x[type];
            else current_cost += y[type];

            if (money_left >= current_cost) {
                dfs(type + 1, money_left - current_cost, candies + k);
            } else {
                break; // 钱不够了，不用往下试了
            }
        }
    }

    void solve() {
        max_candies = 0;
        dfs(1, m, 0);
        cout << max_candies << "\n";
    }
}

/* =========================================================
   【防线 2】特殊性质 A (对应 x_i == y_i) -> 稳拿 15 分
   单价永远不变，直接买最便宜的！
========================================================= */
namespace Subtask_A {
    void solve() {
        long long min_price = 2e18; // 极大值
        for (int i = 1; i <= n; i++) {
            min_price = min(min_price, x[i]);
        }
        cout << m / min_price << "\n";
    }
}

/* =========================================================
   【防线 3】特殊性质 B (对应 x_i >= y_i) -> 稳拿 25 分
   第一颗贵，第二颗便宜。捆绑销售策略！
========================================================= */
namespace Subtask_B {
    void solve() {
        // pair<礼盒总价, 糖果种类>
        vector<pair<long long, int>> boxes; 
        for (int i = 1; i <= n; i++) {
            boxes.push_back({x[i] + y[i], i});
        }
        // 按照礼盒价格从小到大排序
        sort(boxes.begin(), boxes.end());

        long long money_left = m;
        long long total_candies = 0;

        // 贪心买礼盒（每次买 2 颗）
        long long cheapest_box = boxes[0].first;
        if (money_left >= cheapest_box) {
            long long buy_pairs = money_left / cheapest_box;
            total_candies += buy_pairs * 2;
            money_left %= cheapest_box;
        }

        // 最后剩下的钱，看看还能不能再抠出一颗单品（买一颗）
        long long min_single = 2e18;
        for (int i = 1; i <= n; i++) {
            min_single = min(min_single, x[i]);
        }
        if (money_left >= min_single) {
            total_candies += 1;
        }

        cout << total_candies << "\n";
    }
}

/* =========================================================
   【总指挥部】智能路由，兵力分配
========================================================= */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    bool is_A = true, is_B = true;

    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        if (x[i] != y[i]) is_A = false;
        if (x[i] < y[i]) is_B = false;
    }

    // --- 考场保命路由逻辑 ---
    if (m <= 20) {
        Subtask_DFS::solve(); // 优先保证极小数据的正确率 (25分)
    } 
    else if (is_A) {
        Subtask_A::solve();   // 特殊性质 A (15分)
    } 
    else if (is_B) {
        Subtask_B::solve();   // 特殊性质 B (25分)
    } 
    else {
        // 如果遇到了没有任何性质的大数据（比如 N=10^5），且想不出正解
        // 不要交白卷！调用性质B的代码强行输出，因为性质B的逻辑有概率能骗过随机数据！
        // （运气好能再多混 5~10 分）
        Subtask_B::solve(); 
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n, m;
int G[15][15];

// ---------------------------------------------------------
// 暴力抢分防线：DFS + 最优性剪枝 (预期得分：40 ~ 70分)
// ---------------------------------------------------------
namespace Subtask_DFS_Pruning {
    int min_cost = INF;
    int depth[15]; // 记录每个点在生成树中的深度
    bool vis[15];  // 记录每个点是否已经加入树中

    // cnt: 当前树中的节点数; current_cost: 当前的总花费
    void dfs(int cnt, int current_cost) {
        // 【核心考点：最优性剪枝】
        // 如果当前花费已经 >= 已知的最小花费，直接放弃这条搜索分支！
        // 教练批注：就这一行代码，能让这题的分数从 20分 飙升到 70分！
        if (current_cost >= min_cost) return; 

        // 找齐了 n 个点，更新答案
        if (cnt == n) {
            min_cost = min(min_cost, current_cost);
            return;
        }

        // 枚举下一个要加入树的节点 i
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                // 枚举树中已经存在的节点 j，尝试把 i 接在 j 下面
                for (int j = 1; j <= n; j++) {
                    if (vis[j] && G[j][i] != INF) {
                        vis[i] = true;
                        depth[i] = depth[j] + 1;
                      
                        // 往下搜，代价增加：边权 * 父亲节点的深度
                        dfs(cnt + 1, current_cost + G[j][i] * depth[j]);
                      
                        // 回溯，恢复现场
                        vis[i] = false;
                        depth[i] = 0;
                    }
                }
            }
        }
    }

    void solve() {
        // 枚举哪个点作为挖掘的起点（根节点）
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof(vis));
            memset(depth, 0, sizeof(depth));
            vis[i] = true;
            depth[i] = 1; // 根节点深度为 1
            dfs(1, 0);
        }
        cout << min_cost << endl;
    }
}

// ---------------------------------------------------------
// 100分正解：状态压缩 DP 
// ---------------------------------------------------------
namespace Subtask_AC {
    int dp[15][1 << 12]; // dp[深度][状态]
    int trans[1 << 12][1 << 12]; // 预处理状态转移代价
    void solve() {
        // (篇幅原因，省略预处理和 DP 转移代码，主抓暴力教学)
        // 考场上如果 DP 调不出来，马上切回上面的 DFS 拿 70 分！
    }
}

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i != j) G[i][j] = INF;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = min(G[u][v], w); // 注意处理重边
    }

    if (n <= 10) { // 考场分治策略：N较小时用DFS保底
        Subtask_DFS_Pruning::solve();
    } else {
        // Subtask_AC::solve();
        Subtask_DFS_Pruning::solve(); // 实际上这题数据极水，剪枝DFS能过绝大多数点
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int a[20][20], n, m;
int dp[20][1 << 15];
int b[1 << 15];
int mi[1 << 15][20];

struct node {
	int x, y;
};
vector<node>g[1 << 15];
map<int, map<int, int>>mp;

signed main() {
	cin >> n >> m;
	memset(mi, 0x3f3f3f3f, sizeof(mi));
	memset(a, 0x3f3f3f, sizeof(a));
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		a[u][v] = a[v][u] = min(a[u][v], w);
		mp[u][v] = mp[v][u] = 1;
	}
	for (int i = 1; i <= n; i++)
		a[i][i] = 0;
	for (int i = 0; i <= (1 << n) - 1; i++) {
		b[i] = i;
		for (int j = 1; j <= n; j++) {
			if (i & (1 << (j - 1))) {
				for (int k = 1; k <= n; k++) {
					if (!(i & (1 << (k - 1)))) {
						if (mp[j][k]) {
							b[i] |= (1 << (k - 1));
							mi[i][k] = min(mi[i][k], a[j][k]);
						}

					}
				}
			}
		}
	}
	for (int i = 0; i <= (1 << n) - 1; i++) {
		for (int j = i; j; j = (j - 1)&i) {
			if ((i & b[j]) == i && i != j) {
				int sum = 0;
				int bt = i ^ j;
				for (int k = 1; k <= n; k++) {
					if (bt & (1 << (k - 1))) {
						sum += mi[j][k];
					}
				}
				g[i].push_back({j, sum});
			}

		}
	}
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	for (int i = 0; i < n; i++) {
		dp[1][1 << i] = 0;
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= (1 << n) - 1; j++) {
			for (auto V : g[j]) {
				//	cout<<V.x<<" "<<V.y<<endl;
				dp[i][j] = min(dp[i][j], dp[i - 1][V.x] + (i - 1) * V.y);
			}
		}
	}
	int ans = 1e18;
	for (int i = 1; i <= n; i++)
		ans = min(ans, dp[i][(1 << n) - 1]);
	cout << ans;
	return 0;
}

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-8;

int n, m;
double X[20], Y[20];

// 记录当前已经成型的抛物线方程 y = ax^2 + bx
double pa[20], pb[20];
int p_cnt = 0; // 当前成型抛物线的数量

// 记录当前只打了一只猪，还在等待配对的"单身猪"
double sx[20], sy[20];
int s_cnt = 0; // 当前单身猪的数量

int ans; // 记录全局最少需要的鸟数

// 工具函数：解方程求 a 和 b
bool get_parabola(double x1, double y1, double x2, double y2, double &a, double &b) {
    if (abs(x1 - x2) < eps) return false; // 同一竖线，不行
    double y1_x1 = y1 / x1;
    double y2_x2 = y2 / x2;
    a = (y1_x1 - y2_x2) / (x1 - x2);
    b = y1_x1 - a * x1;
    return a < -eps; // 必须开口向下
}

// DFS核心：u 表示当前正在决定第 u 只猪的命运，birds 表示目前总共花了多少只鸟
void dfs(int u, int birds) {
    // 【灵魂剪枝 1：最优性剪枝】
    // 如果当前用的鸟已经 >= 目前已知的最优解，说明这条路是死路，赶紧回头！
    if (birds >= ans) return;

    // 边界条件：所有猪都处理完了
    if (u == n) {
        ans = min(ans, birds);
        return;
    }

    // ---------------------------------------------------------
    // 选择 1：【白嫖】看看能不能被已经成型的抛物线顺路打死
    // ---------------------------------------------------------
    for (int i = 0; i < p_cnt; i++) {
        double expected_y = pa[i] * X[u] * X[u] + pb[i] * X[u];
        if (abs(expected_y - Y[u]) < eps) {
            // 【灵魂剪枝 2：贪心剪枝】(极其重要！！！)
            // 如果它能被现成的抛物线打死，千万别再浪费鸟去打它了！
            // 直接处理下一只猪，并且 return 断绝其他浪费的选择！
            dfs(u + 1, birds);
            return; 
        }
    }

    // ---------------------------------------------------------
    // 选择 2：【凑对子】跟前面的某只"单身猪"组队，确立新的抛物线
    // ---------------------------------------------------------
    for (int i = 0; i < s_cnt; i++) {
        double a, b;
        if (get_parabola(sx[i], sy[i], X[u], Y[u], a, b)) {
            // 凑对成功！开始修改状态 (准备往下搜)
            
            // 1. 保存当前的单身猪坐标，用于回溯
            double old_x = sx[i], old_y = sy[i];
            
            // 2. 把这只单身猪从单身阵营删除 (O(1) 删除法：用最后一个元素覆盖它)
            sx[i] = sx[s_cnt - 1];
            sy[i] = sy[s_cnt - 1];
            s_cnt--;
            
            // 3. 把新凑出的抛物线加入成型阵营
            pa[p_cnt] = a;
            pb[p_cnt] = b;
            p_cnt++;
            
            // 4. 往下搜！注意：birds 数量不变，因为单身猪那一发鸟只是变成了抛物线
            dfs(u + 1, birds);
            
            // 5. 【回溯】恢复现场！(搜完退回来，当作无事发生)
            p_cnt--;
            s_cnt++;
            sx[i] = old_x;
            sy[i] = old_y;
        }
    }

    // ---------------------------------------------------------
    // 选择 3：【开新坑】实在不行，我自己单独用一只新鸟！变成单身猪
    // ---------------------------------------------------------
    sx[s_cnt] = X[u];
    sy[s_cnt] = Y[u];
    s_cnt++;
    
    // 因为用了新鸟，所以 birds + 1
    dfs(u + 1, birds + 1);
    
    // 【回溯】恢复现场
    s_cnt--;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> X[i] >> Y[i];
    
    ans = 100; // 每组数据初始化为一个很大的值
    p_cnt = 0;
    s_cnt = 0;
    
    // 从第 0 只猪开始处理，当前用了 0 只鸟
    dfs(0, 0); 
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}