#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1000000000000000000LL;
const int N = 605;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m, n;
cin >> m >> n;
vector<array<int, 4>> devices(m);
set<int> values;
values.insert(1);
values.insert(n);
for (int i = 0; i < m; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
devices[i][0] = a;
values.insert(a);
devices[i][1] = b;
values.insert(b);
values.insert(c);
devices[i][2] = c;
devices[i][3] = d;
}
map<int, int> to;
int curTo = 1;
for (int i : values)
{
to[i] = curTo;
curTo++;
}
n = to[n];
for (auto& device : devices)
{
for (int i = 0; i <= 2; i++) device[i] = to[device[i]];
}
ll dp[N][N];
for (int i = 0; i <N; i++) for (int j = 0; j < N; j++) dp[i][j] = M;
for (int i = m - 1; i >= 0; i--)
{
int x = devices[i][0];
int y = devices[i][1];
int c = devices[i][2];
int d = devices[i][3];
dp[x][y] = min<ll>(dp[x][y], d);
for (int j = 1; j <= n; j++)
{
for (int k = j; k <= n; k++)
{
if (c >= j && c <= k)
{
dp[min(j, x)][max(k, y)] = min(dp[min(j, x)][max(k, y)], dp[j][k] + d);
}
}
}
}
if (dp[1][n] == M) cout << -1 << "\n";
else cout << dp[1][n] << "\n";
}
/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/
/*
6 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
1 5 1 4
*/
/*
3 5
2 4 3 10
1 3 1 20
2 5 4 30
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
