这个题听说二分，但是我太菜不会二分，我就会模拟做qwq，时间复杂度O(nk)

我们可以先预处理出所有花费不超过p的咖啡厅，然后预处理一下各色客栈的前缀和。

之后我们假设咖啡厅左边及自己共有li间i色客栈，右边有ri间i色客栈，那么答案应该加上li*ri。但是我们发现这样是会漏掉一种情况的，当这家咖啡厅所在的客栈作为右边被人居住的客栈的时候，我们会漏算。因此我们需要for两边第一遍处理li*ri的情况，第二遍再单独处理咖啡厅作为右端点的情况。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long lo;lo n,k,p,x,se[200020],s[200020][50],ans,wei[200020],tot;int main(){    scanf("%lld%lld%lld",&n,&k,&p);     for(int i=1;i<=n;i++)    {        scanf("%lld%lld",&se[i],&x);        if(x<=p)//记录下所有的消费小于p的咖啡厅             wei[++tot]=i;    }    for(int i=1;i<=n;i++)//统计下前缀和     {        for(int j=0;j