算[l, r]区间里所有子区间最小值的和。
对每个位置i向左知道第一个小于它的位置，向右找到第一个小于它的位置，算算贡献。
考虑可以用单调栈算。
但是如果一个区间里同一个最小值出现多次就挂了，所以考虑魔改一下，对于右边找到第一个小于它的点，对于左边找到第一个小于等于它的点并记录位置，这样的话就相当于只算了区间里第一次出现的点的贡献。
stack[++top][1] = 1; stack[top][0] = 0;
for (int i = 2; i <= l; i++)
{
while (top && height[i] < stack[top][0]) ri[stack[top--][1]] = i;
le[i] = stack[top][1]; stack[++top][1] = i; stack[top][0] = height[i];
}
while (top) ri[stack[top--][1]] = l + 1;
SA插入特殊值的时候最好插1
给出数列(f_1 dots f_n)
(T)组询问，每次给定(n)，(m)，求(sum_{i = 1}^{n} sum_{j = 1}^{m} f_{gcd(i, j)})
令(g = mu ast f)
求(g)的方法
void get_g_3(int N, const int *f, int *g) {
for (int i = 1; i <= N; i++) g[i] = f[i];
for (int i = 0; i < prime_count; i++)
for (int j = N / prime[i]; j >= 1; j--)
g[j * prime[i]] = (g[j * prime[i]] - g[j]) % mod;
} // Magic! O(nloglogn)
群直积的卷积变换可以分解成独立的卷积变换
定义函数(f_p(n)=n==p^k?f(n):0)
所以积性函数(f = f_2 ast f_3 ast f_5 dots f_n)
这是因为可以将积性函数(f)按质因子拆开，根据定义只有一种情况也就是(n)的每个质因子分别在对应的函数里的时候会对(f)的值产生贡献。
那么如何算这个群卷积呢？
考虑对于前(n)个可以变成前(n - 1)个的卷积和第(n)个的卷积卷起来。
发现只有在第(n)个函数传进去的参数是(p ^ k)的时候才会产生贡献，于是枚举转移即可。
令
定义乘法为狄利克雷卷积，那么有
这是因为
而所有(f_p)的卷积就对应于(n)的分解中每一项的积
或者更直接地，使用DGF，有
复杂度证明(重要)
假设算任意数列(f)和积性函数(g)的卷积，这样做的复杂度实际上是
在平面直角坐标系中，横坐标之差为(w)，纵坐标之差为(h)的两个点之间的连线上有(gcd(w, h) - 1)个点。
假设((x, y))为直线上的点，当且仅当(x imes frac{h}{w})为整数。
也就是说，(w | h * x)，设(x' = w / gcd(w, h))，(y' = h / gcd(w, h))，则此时(gcd(x', y') = 1)，且(w | h * x)当且仅当(x' | y' * x)，由于(gcd(x', y') = 1)，故上式等价于(x' | x)，由于(0 leqslant x leqslant w)，且(x' | w)。
所以合法点数为
去掉两个端点，则有(gcd(w, h) - 1)个点。
一个字符串的(border)可以分成(log(|S|))组，每组为(AB^k)的形式，按长度(> frac{i}{2})和不大于来分。
取模非常的慢，所以要进行取模优化。
对于加法：
void Qm(int &x) { if (x >= MOD) x -= MOD; return; }
对于减法：
void Qm(int &x) { x += x >> 31 & MOD; return; }
粘一个(RainAir)神仙的(Fread)代码：
inline char nc(){
#define SIZE 1000000+3
static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
if(p1 == p2){
p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
if(p1 == p2) return -1;
}
return *p1++;
#undef SIZE
}
template <typename T>
inline void read(T &x){
x = 0;int flag = 0;char ch = nc();
while(!isdigit(ch)){
if(ch == '-') flag = 1;
ch = nc();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + (ch^'0');
ch = nc();
}
if(flag) x = -x;
}
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define MP std::make_pair
#define PII std::pair<int, int>
#define all(x) (x).begin(), (x).end()
#define CL(a, b) memset(a, b, sizeof a)
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(x, a) for (int x = head[a]; x; x = edge[x].next)
typedef long long ll;
template <class T>
inline void rd(T &x) {
char c = getchar(), f = 0;
x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}
const int MAXN = 1000 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
std::vector<int> set[MAXN * 3];
int c[MAXN * 3], tp[MAXN * 3], sm[MAXN * 3];
ll del[MAXN][MAXN * 3], f[MAXN][MAXN * 3];
int sc[MAXN][MAXN * 3], cost[MAXN * 3];
int main() {
rd(n);
rd(m);
rd(k);
rep(i, 1, n) {
int b, a;
rd(a);
rd(b);
rd(c[i]);
set[c[i]].pb(a);
}
rep(i, 1, m) rd(cost[i]);
ll tot = 0;
rep(i, 1, m) {
std::sort(all(set[i]));
for (int j = 0, jj; j < set[i].size(); j = jj) {
jj = j;
while (jj < set[i].size() && set[i][j] == set[i][jj]) jj++;
sc[i][++tp[i]] = jj - j;
}
sm[i] = set[i].size();
std::sort(sc[i] + 1, sc[i] + tp[i] + 1);
std::reverse(sc[i] + 1, sc[i] + tp[i] + 1);//找出每个斜率的直线个数并从大到小排序。
int pres = 0;
ll prod = 0, sum = 0;
rep(j, 1, tp[i]) {
rep(jj, 1, sc[i][j]) del[i][pres + jj] = prod, tot += prod;//当最后的这些删去的时候只能影响到更靠后的了，就是这个prod，即从前面的中任选两条直线。
pres += sc[i][j];
prod += 1ll * sum * sc[i][j];//更新从一些直线里面任选两条。
sum += sc[i][j];//更新sum。
}
std::sort(del[i] + 1, del[i] + sm[i] + 1);
std::reverse(del[i] + 1, del[i] + sm[i] + 1);
rep(j, 1, sm[i]) del[i][j] += del[i][j - 1];//从大到小排序，前缀和算出删掉j条直线能去掉的三角形数量。
}
ll mx = 0;
CL(f, ~0x3f);
f[0][0] = 0;
rep(i, 1, m) {
rep(j, 0, k) for (int jj = 0; jj * cost[i] <= j && jj <= sm[i]; jj++)
f[i][j] = std::max(f[i][j], f[i - 1][j - jj * cost[i]] + del[i][jj]);
}//跑分组背包。
rep(i, 0, k) mx = std::max(mx, f[m][i]);
printf("%lld
", tot - mx);
return 0;
}