思路是 $dp_{i,s,lst}$ 表示上一次涂了 lst 这一次涂了 i 此时的状态为 s 的最小值

转移

dp[i][s][k]=min{dp[k][s'][l]+(C[i].col!=C[k].col)}

//Template By (HMS_Cheshire)小柴郡喵喵喵
#include<bits/stdc++.h>
using namespace std;
using lll = __int128;
using ll = long long;
namespace Mashiro {
    char buf[1<<18],*p1=buf,*p2=buf;
    inline int getc() {
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
    }
#define getc() getchar()
    template<typename T>inline void read(T& x) {
        x=0;int f=1;
        char ch=getc();
        while(!isdigit(ch)){if(ch=='-')f=~f+1;ch=getc();}
        while (isdigit (ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getc();}
        x*=f;
    }
    template <typename T,typename... Args> inline void read(T& x, Args&... args) {
        read(x);
        read(args...);
    }
    char buffer[1<<18];int p11=-1;const int p22=(1<<18)-1;
    inline void flush() {fwrite(buffer,1,p11+1,stdout),p11=-1;}
    inline void putc(const char &x) {if (p11==p22) flush();buffer[++p11]=x;}
    template<typename T>inline void write(T x) {
        static int buf[40],top=0;
        if(x<0)putc('-'),x=~x+1;
        while(x)buf[++top]=x%10,x/=10;
        if(top==0)buf[++top]=0;
        while (top) putc(buf[top--]^48);
        putc(' ');
        flush();
     }
     template <typename T,typename... Args> inline void write(T x, Args... args) {
         write(x);
         write(args...);
     }
}
using namespace Mashiro;
const int maxn=17;
const int maxs=(1<<16);
int n,S;
struct cfx{
	int sx,sy,ex,ey,col;
}C[maxn];
int dp[maxn][maxs][maxn];
vector<int>On[maxn];
int state[maxn]; 
int can[maxs],vis[maxs];
//addr Type
// Type - 0 On
// Type - 1 Nearby
vector<int>Lst[maxs];
inline bool check(int x,int y){
	return x==(x|y);
}
int main(){
	read(n);
	S=(1<<n)-1;
	for(int i(1);i<=n;++i){
		read(C[i].sy,C[i].sx,C[i].ey,C[i].ex,C[i].col);
	}
	for(int i(1);i<=n;++i){
		for(int j(0);j<n;++j){
			if(i==j)continue;
			if(C[i].sy==C[j].ey){
				if((C[j].ex<=C[i].sx)||(C[j].sx>=C[i].ex)){
					
				}
				else {
					On[i].emplace_back(j);
					state[i]+=(1<<j-1);
				}
			}
		}
	}
	can[0]=1;
	for(int i(1);i<=S;++i){
		for(int j(1);j<=n;++j){
			if(check(i,state[j])&&((i&(1<<j-1)))&&can[(i^(1<<j-1))]){
				can[i]=1;
				Lst[i].emplace_back(j);
				
			}
		}
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][0][0]=0;
	for(int i(1);i<=n;++i){
		if(state[i]==0){
			dp[i][1<<i-1][0]=1;
			vis[1<<i-1]=1;
		}
	}
//dp[i][s][k]=min{dp[k][s'][l]+(C[i].col!=C[k].col)}
	Lst[0].emplace_back(0);
	for(int i(1);i<S;++i){
		if(!can[i])continue;
		for(int j(1);j<=n;++j){
			if((i&(1<<j-1)))continue;
			if(!check(i,state[j]))continue;
			for(int k:Lst[i]){
				int ss=(i^(1<<k-1));
				for(int l:Lst[ss]){
					dp[j][i^(1<<j-1)][k]=min(dp[j][i^(1<<j-1)][k],dp[k][i][l]+(C[j].col!=C[k].col));
				}
			}
		}
	}
	int ans=1e9;
	for(int i:Lst[S]){
		int ss=(S^(1<<i-1));
		for(int j:Lst[ss]){
			ans=min(ans,dp[i][S][j]);
		}
	}
	write(ans);
	return 0;
}