1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 100000 + 10; 8 int x[maxn], y[maxn]; 9 int total_dist[maxn], total_weight[maxn], dist2origin[maxn];10 int q[maxn], d[maxn];11 12 int func(int i)13 {14     return d[i] - total_dist[i+1] + dist2origin[i+1];15 }16 17 int main(void)18 {19     #ifdef LOCAL20         freopen("3983in.txt", "r", stdin);21     #endif22 23     int T;24     scanf("%d", &T);25     while(T--)26     {27         int c, n, w, front, rear;28         scanf("%d%d", &c, &n);29         total_dist[0] = total_weight[0] = x[0] = y[0] = 0;30         for(int i = 1; i <= n; ++i)31         {32             scanf("%d%d%d", &x[i], &y[i], &w);33             dist2origin[i] = x[i] + y[i];34             total_dist[i] = total_dist[i-1] + abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);35             total_weight[i] = total_weight[i-1] + w;36         }37         front = rear = 1;38         for(int i = 1; i <= n; ++i)39         {40             while(front <= rear && total_weight[i] - total_weight[q[front]] > c)41                 ++front;42             d[i] = func(q[front]) + total_dist[i] + dist2origin[i];43             while(front <= rear && func(q[rear]) >= func(i))44                 --rear;45             q[++rear] = i;46         }47         printf("%d\n", d[n]);48         if(T)    printf("\n");49     }50     return 0;51 }