#include <iostream>
#include <algorithm>
#include <vector>
struct Reindex
{
Reindex(int d, int e, int p) : device(d), elem(e), pos(p) {}
int device, elem, pos;
bool operator <(const Reindex &other) const
{
return (pos < other.pos);
}
};
const int MAXN = 1e5;
const long long INFTY = 1e18;
const int LEAVES = 1 << 19;
const int TSIZE = LEAVES << 1;
int left[MAXN], right[MAXN];
int drop[MAXN];
int cost[MAXN];
std::vector<Reindex> compress;
long long tree[TSIZE];
long long getLeft[MAXN];
long long getRight[MAXN];
void reset()
{
std::fill_n(tree, TSIZE, INFTY);
}
void upd(int node, long long val)
{
tree[node] = std::min(tree[node], val);
if (node > 1)
upd(node / 2, val);
}
long long req(int leftNode, int rightNode)
{
long long ans = INFTY;
if (leftNode % 2 == 1)
ans = std::min(ans, tree[leftNode++]);
if (rightNode % 2 == 1)
ans = std::min(ans, tree[--rightNode]);
if (leftNode < rightNode)
ans = std::min(ans, req(leftNode / 2, rightNode / 2));
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
int lines, columns;
std::cin >> lines >> columns;
for (int iDevice = 0; iDevice < lines; iDevice++)
{
std::cin >> left[iDevice] >> right[iDevice] >> drop[iDevice] >> cost[iDevice];
compress.emplace_back(iDevice, 0, left[iDevice] - 1);
compress.emplace_back(iDevice, 1, right[iDevice] - 1);
compress.emplace_back(iDevice, 2, drop[iDevice] - 1);
}
compress.emplace_back(-1, -1, 0);
compress.emplace_back(-1, -1, columns - 1);
std::sort(compress.begin(), compress.end());
int trueCol = 0;
for (int iElem = 0; iElem < (int)compress.size(); trueCol++)
for (int jElem = iElem; iElem < (int)compress.size() && compress[iElem].pos == compress[jElem].pos; iElem++)
{
if (compress[iElem].elem == 0)
left[compress[iElem].device] = trueCol;
else if (compress[iElem].elem == 1)
right[compress[iElem].device] = trueCol + 1;
else if (compress[iElem].elem == 2)
drop[compress[iElem].device] = trueCol;
}
reset();
upd(LEAVES, 0);
for (int iDev = 0; iDev < lines; iDev++)
{
getLeft[iDev] = req(LEAVES + left[iDev], LEAVES + right[iDev]);
upd(LEAVES + drop[iDev], getLeft[iDev] + cost[iDev]);
}
reset();
upd(LEAVES + trueCol - 1, 0);
for (int iDev = 0; iDev < lines; iDev++)
{
getRight[iDev] = req(LEAVES + left[iDev], LEAVES + right[iDev]);
upd(LEAVES + drop[iDev], getRight[iDev] + cost[iDev]);
}
long long minCost = INFTY;
for (int iDev = 0; iDev < lines; iDev++)
minCost = std::min(minCost, getLeft[iDev] + getRight[iDev] + cost[iDev]);
if (minCost == INFTY)
std::cout << "-1\n";
else
std::cout << minCost << '\n';
return 0;
}
