Cod sursa(job #137623)
#include <stdio.h>
#define NMAX (1<<17)
#define MIN(a,b) (((a)<(b))?(a):(b))
int N;
long long A[NMAX], C[NMAX], X[NMAX], D[NMAX], S[NMAX], LLINF;
void read()
{
int i;
freopen("stalpi.in", "r", stdin);
scanf("%d", &N);
for (i = 1; i <= N; i++)
scanf("%lld%lld%lld%lld", X+i, C+i, S+i, D+i);
}
void brut()
{
int i, j, k1, k2, p, q, md;
long long d=2147483647, aux;
for (i = 1; i <= N; i++)
for (j = i+1; j <= N; j++)
if (X[i]>X[j])
{
aux = X[i], X[i] = X[j], X[j] = aux;
aux = C[i], C[i] = C[j], C[j] = aux;
aux = S[i], S[i] = S[j], S[j] = aux;
aux = D[i], D[i] = D[j], D[j] = aux;
}
LLINF = d*d;
X[0] = X[1]-1;
X[N+1] = X[N]+1;
A[1] = C[1];
for (i = 2; i <= N+1; i++)
{
A[i] = LLINF;
for (j = 0; j < i; j++)
{
p = j; q = N+1;
d = X[j]+D[j];
k1 = j;
while (q-p>=0)
{
md = (p+q)>>1;
if (X[md]>d) q = md-1;
else p = md+1, k1 = md;
}
p = 0; q = i;
d = X[i]-S[i];
k2 = i;
while (q-p>=0)
{
md = (p+q)>>1;
if (X[md]<d) p = md+1;
else q = md-1, k2 = md;
}
if (k1>=k2-1)
A[i] = MIN(A[i], A[j]+C[i]);
}
}
}
void write()
{
freopen("stalpi.out", "w", stdout);
printf("%d\n", A[N+1]);
}
int main()
{
read();
brut();
write();
return 0;
}