#define FOLD__SCOPE                                                          
                                                                             
#ifdef  FOLD__SCOPE   /// includes                                           
                                                                             
#include <fstream>                                                           
#include <vector>                                                            
#include <limits>                                                            
#include <algorithm>                                                         
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// typedefs                                           
                                                                             
typedef  ::std::size_t  stsz;                                                
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// birt                                               
                                                                             
/// birt ― [B] components [i]ncreasing st[r]uc[t]                            
                                                                             
struct birt                                                                  
{                                                                            
  stsz  A;                                                                   
  stsz  B;                                                                   
  stsz  I;                                                                   
  stsz  X;                                                                   
  stsz  M;                                                                   
                                                                             
  birt() noexcept : A(0), B(0), I(0), X(0), M(0) { }                         
};                                                                           
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// comparator                                         
                                                                             
/// Comparator for sorting the C sequence increasingly by ending times.      
                                                                             
bool                                                                         
increasinglyByEndingTimes                                                    
(                                                                            
  birt const  & u                                                            
, birt const  & v                                                            
)                                                                            
noexcept                                                                     
{                                                                            
  return u.B < v.B;                                                          
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// airt                                               
                                                                             
/// airt ― [A] components [i]ncreasing s[t]ruc[t]                            
                                                                             
struct airt                                                                  
{                                                                            
  stsz  A;                                                                   
  stsz  I;                                                                   
                                                                             
  airt () noexcept : A(0), I(0) { }                                          
                                                                             
};                                                                           
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// comparator                                         
                                                                             
/// Comparator for sorting the D vector increasingly by starting times.      
                                                                             
bool                                                                         
increasinglyByStartingTimes                                                  
(                                                                            
  airt const  & u                                                            
, airt const  & v                                                            
)                                                                            
noexcept                                                                     
{                                                                            
  return u.A < v.A;                                                          
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// typedefs                                           
                                                                             
typedef  ::std::vector < birt >  vtbi;                                       
typedef  ::std::vector < airt >  vtai;                                       
                                                                             
typedef  ::std::ifstream  stis;                                              
typedef  ::std::ofstream  stos;                                              
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// demo                                               
                                                                             
bool                                                                         
demo                                                                         
()                                                                           
{                                                                            
  #ifdef  FOLD__SCOPE /// state                                              
                                                                             
  vtbi  C;                                                                   
  vtai  D;                                                                   
                                                                             
  #endif                                                                     
  if (true) {         /// read                                               
                                                                             
    /// Verify implementation limits.                                        
    /// Read the input.                                                      
    /// Validate it.                                                         
    /// Aquire space.                                                        
    /// Fail fast.                                                           
                                                                             
    stsz  const max_s = ::std::numeric_limits < stsz > :: max (  ) ;         
                                                                             
    stsz  const min_n = 1;                                                   
    stsz  const max_n = 100000;                                              
                                                                             
    stsz  const min_t = 1;                                                   
    stsz  const max_t = 1000000000;                                          
                                                                             
    bool  ok = false;                                                        
                                                                             
    ok = ( (1 == min_n) && (min_n <= max_n) &&                               
           (max_n == 100000) && (100000 <= max_s) &&                         
           (1 == min_t) && (min_t <= max_t) &&                               
           (max_t == 1000000000) && (1000000000 <= max_s)  );                
                                                                             
    if ( ! ok  )                                                             
    {                                                                        
      /// Implementation limits.                                             
      return false;                                                          
    }                                                                        
                                                                             
    stis  is ("heavymetal.in");                                              
                                                                             
    stsz  n;                                                                 
    is >> n;                                                                 
                                                                             
    ok = ( (min_n <= n) && (max_n >= n)  );                                  
                                                                             
    if ( ! ok  )                                                             
    {                                                                        
      /// Invalid input.                                                     
      return false;                                                          
    }                                                                        
                                                                             
    vtbi  c(n);                                                              
    vtai  d(n);                                                              
                                                                             
    stsz  i = 0;                                                             
    stsz  a = 0;                                                             
    stsz  b = 0;                                                             
                                                                             
    for ( i = 0; n > i; ++ i  )                                              
    {                                                                        
      is >> a >> b;                                                          
                                                                             
      ok = ( (min_t <= a) && (a < b) && (max_t >= b)  );                     
                                                                             
      if ( ! ok  )                                                           
      {                                                                      
        /// Invalid input.                                                   
        return false;                                                        
      }                                                                      
                                                                             
      c[i].A = a;                                                            
      c[i].B = b;                                                            
                                                                             
    }                                                                        
                                                                             
    /// So far so good.                                                      
    C.swap(c);                                                               
    D.swap(d);                                                               
                                                                             
  }                                                                          
  if (true) {         /// solve                                              
                                                                             
    /// Solve problem instance.                                              
                                                                             
    if (true) {  /// Sort the concerts increasingly by their ending times.   
                                                                             
      ::std::sort(C.begin(), C.end(), increasinglyByEndingTimes);            
                                                                             
    }                                                                        
    if (true) {  /// Sort the concerts increasingly by their starting times. 
                                                                             
      stsz  const n = C.size();                                              
                                                                             
      stsz  i = 0;                                                           
                                                                             
      for (i = 0; n > i; ++ i  )                                             
      {                                                                      
        D[i].A = C[i].A;                                                     
        D[i].I = i;                                                          
      }                                                                      
                                                                             
      ::std::sort(D.begin(), D.end(), increasinglyByStartingTimes);          
                                                                             
    }                                                                        
    if (true) {  /// Link each concert to the closest preceding concert.     
                                                                             
      stsz  const n = C.size();  stsz  i = 0;  stsz  j = 0;                  
                                                                             
      for ( j = 0; n > j; ++ j  )                                            
      {                                                                      
                                                                             
        while (C[i].B <= D[j].A)                                             
        {                                                                    
          ++ i;                                                              
        }                                                                    
                                                                             
        C[D[j].I].I = i;                                                     
                                                                             
      }                                                                      
                                                                             
    }                                                                        
    if (true) {  /// Dynamic programming for the win!                        
                                                                             
      /// Bestⱼ ← (Bⱼ − Aⱼ) + max i←0…n−1, Bᵢ ≤ Aⱼ ∷ Bestᵢ,                  
      /// and we use that i must be less than j, and the link from j, to     
      /// max i, the link that we have computed in the previous step!        
      ///                                                                    
      /// At step j, C[j].X ← Bestⱼ                                          
      ///            C[j].M ← max i ← 0…j ∷ Bestⱼ.                           
                                                                             
      stsz  const n = C.size();                                              
                                                                             
      stsz  j = 0;  stsz  i = 0;  stsz  b = 0;  stsz  a = 0;                 
                                  stsz  x = 0;  stsz  m = 0;                 
                                                                             
      for (j = 0; n > j; ++ j)                                               
      {                                                                      
        i = C[j].I;  b = C[j].B;  a = C[j].A;                                
        x = (b - a) + ( (0 < i) ? (C[i-1].M) : 0  );                         
        m = (0 < j) ? ( ::std::max(x, C[j-1].M) ) : x;                       
        C[j].X = x; C[j].M = m;                                              
      }                                                                      
                                                                             
    }                                                                        
                                                                             
  }                                                                          
  if (true) {         /// write                                              
                                                                             
    stsz  const n = C.size();                                                
    stsz  const z = C[n-1].M;                                                
                                                                             
    stos  os("heavymetal.out");                                              
    os << z << '\n';                                                         
                                                                             
  }                                                                          
                                                                             
  return true;                                                               
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE   /// main                                               
                                                                             
                                                                             
int                                                                          
main                                                                         
()                                                                           
{                                                                            
  int  status = 2;                                                           
                                                                             
  try                                                                        
  {                                                                          
    bool  const ok = demo();                                                 
    status = ( ok ? 0 : 1 );                                                 
  }                                                                          
  catch ( ... )                                                              
  {                                                                          
    status = 3;                                                              
  }                                                                          
                                                                             
  return status;                                                             
}                                                                            
                                                                             
                                                                             
#endif