#include <vector>
#include <iostream>
#include <complex>
#include <cmath>
using namespace std;
typedef complex<double> P;
typedef pair<P, double> C;
#define X real()
#define Y imag()

const double pi = acos(-1), EPS = (1e-7);

double dot(P a, P b){
  return a.X*b.X + a.Y*b.Y;
}

vector<P> cpcc(C a, C b){
  //円と円の交点
  double d = abs(a.first-b.first), ra = a.second, rb = b.second;
  double t = (ra*ra-rb*rb+d*d)/2/d, h = sqrt(ra*ra-t*t);
  P m = t/abs(b.first-a.first)*(b.first-a.first)+a.first;
  vector<P> cp(2,m);
  P n = (a.first-b.first)*P(0,1);
  n /= abs(n);
  cp[0] -= h*n;
  cp[1] += h*n;
  return cp;
}

vector<P> tangent_to_C(P p, C c){
  //点pから円cに伸ばした接線の接点を求める
  C c2 = C((p+c.first)/2.0,abs(p-c.first)/2.0);
  return cpcc(c,c2);
}

bool in_sector(P c, double r, double theta, double a, double b){
  if(abs(c) < r + EPS) return false;
  if(abs(c) + r > a + EPS) return false;
  vector<P> cps = tangent_to_C(P(0,0), C(c, r));
  if(cps.empty()) return false;
  P d = P(cos(b), sin(b));
  for(int i = 0; i < (int)cps.size(); ++i){
    P cp = cps[i];
    if(dot(cp, d)/abs(cp) < cos(theta/2) - EPS) return false;
  }
  return true;
}

void dfs(vector< vector<int> > &G, int v, vector<int> &P, vector<int> &R, int t){
  for(int i = 0; i < (int)G[v].size(); ++i){
    int v_ = G[v][i];
    int d = min(P[v_], R[v_]+t) - R[v_];
    R[v_] += d;
    //for(int i = 0; i < (int)R.size(); ++i) cout << R[i] << " ";cout << endl;
    if(d > 0) dfs(G, v_, P, R, d);
  }
}

int solve(vector< vector<int> > &G, vector<int> P){
  int n = G.size();
  vector<int> R(n, 0);
  R[0] = P[0];
  dfs(G, 0, P, R, R[0]);
  //for(int i = 0; i < n; ++i) cout << R[i] << " ";cout << endl;
  return R.back();
}

int main(){
  int N;
  cin >> N;
  double theta, a;
  vector<int> Power(N+2, 0);
  Power.back() = (int)1e9;
  cin >> theta >> a >> Power[0];
  theta *= pi/180.0;
  vector<P> L(N+1);
  vector<double> R(N+1), A(N), T(N), B(N);
  for(int i = 0; i < N; ++i){
    double x, y;
    cin >> x >> y >> R[i] >> T[i] >> A[i] >> B[i] >> Power[i+1];
    L[i] = P(x, y);
    T[i] *= pi/180.0;
    B[i] *= pi/180.0;
  }
  double x, y;
  cin >> x >> y >> R[N];
  L[N] = P(x, y);
  vector< vector<int> > G(N+2);
  for(int i = 0; i < N; ++i){
    for(int j = 0; j <= N; ++j){
      if(i == j) continue;
      if(in_sector(L[j]-L[i], R[j], T[i], A[i], B[i])){
        G[i+1].push_back(j+1);
        //cout << i << " " << j << endl;
      }
    }
  }

  int ans = 0;
  for(int i = 0; i <= N; ++i){
    if(abs(L[i]) + R[i] > a) continue;
    if(abs(L[i]) - R[i] < EPS) continue;
    vector<P> cps = tangent_to_C(P(0,0), C(L[i], R[i]));
    if(cps.empty()) continue;
    P cp = cps[0];
    if(arg(cps[0]) > arg(cps[1])) swap(cps[0], cps[1]);
    double b = arg(cp*P(cos(theta/2), sin(theta/2)));
    G[0] = vector<int>();
    for(int j = 0; j <= N; ++j){
      if(in_sector(L[j], R[j], theta, a, b)){
        G[0].push_back(j+1);
      }
    }
    /*
    cout << "i = " << i << endl;
    for(int j = 0; j < N+2; ++j){
      cout << j << " : ";
      for(int k = 0; k < (int)G[j].size(); ++k) cout << G[j][k] << " ";cout << endl;
    }
    cout << solve(G, Power) << endl;
    */
    ans = max(ans, solve(G, Power));
  }
  cout << ans << endl;
  return 0;
}


### Prompt

Your challenge is to write a cpp solution to the following problem:

Problem

N circular light sources are arranged on a two-dimensional plane. When a light source receives light, the light is emitted in a fan shape from the center point of the light source as shown in the figure below.

<image>
The center point of the light source is represented by (x, y) and the radius is represented by r. The fan shape that becomes light spreads symmetrically in the directions of -θ / 2, + θ / 2 around the angle β, and its radius is α.

When the circle of light source is completely covered by fan-shaped light, the light source is considered to have received that light. The intensity of the light emitted from the light source is the sum of the intensities of the received light. However, there is an upper limit to the intensity of the emitted light, and if the upper limit is exceeded, the intensity of the light will be the same as the upper limit. The light is not blocked by a certain light or light source.

A light source existing at a certain point is used as a target light source. No light is emitted by the target light source, and there is no limit to the intensity of the light received. From coordinates (0,0), you can emit a fan-shaped light of a certain intensity only once in any direction. Create a program to find the maximum value of the total intensity of light received by the target light source. However, it may be assumed that all light sources do not provide input data such that the emitted light returns to the original light source. Also, in this problem, if the distance from the boundary of the area is within 0.000001, it is considered to be on the area.

Constraints

The input satisfies the following conditions.

* All inputs consist of integers
* 1 ≤ n ≤ 100
* -1000 ≤ xi, yi ≤ 1000
* 1 ≤ ri ≤ 1000
* 1 ≤ θi ≤ 180
* 1 ≤ αi ≤ 1000
* 0 ≤ βi <360
* 0 ≤ power, maxpoweri ≤ 1000

Input


n
θ0 α0 power
x1 y1 r1 θ1 α1 β1 maxpower1
..
..
xn yn rn θn αn βn maxpowern
xn + 1 yn + 1 rn + 1


The number n of light sources excluding the target light source is given in the first line.
The information on the coordinates (0,0) that first emit light on the second line, the information on the unintended light source on the third to n + 2 lines, and the information on the target light source on the n + 3 lines are separated by blanks. Given.
For each information, xi and yi are the coordinates of the center point of the light source, ri is the radius of the light source, θi is the angle at which the light spreads, αi is the radius of the light, and βi is the direction in which the light is heading. The power in the second line represents the intensity of the first emitted light, and the maxpoweri in the third to n + second lines represents the upper limit of the emitted light.
The direction βi of light rotates counterclockwise from the positive direction of the x-axis, and the unit of each angle is degrees.

Output

Output the maximum value of the total light intensity that surrounds all the target light sources in one line.

Examples

Input

1
90 10 20
3 3 1 90 10 315 10
6 0 1


Output

30


Input

2
90 10 10
-3 0 1 45 10 90 10
-6 0 2 30 3 180 10
-9 0 1


Output

10

### Response

```cpp
#include <vector>
#include <iostream>
#include <complex>
#include <cmath>
using namespace std;
typedef complex<double> P;
typedef pair<P, double> C;
#define X real()
#define Y imag()

const double pi = acos(-1), EPS = (1e-7);

double dot(P a, P b){
  return a.X*b.X + a.Y*b.Y;
}

vector<P> cpcc(C a, C b){
  //円と円の交点
  double d = abs(a.first-b.first), ra = a.second, rb = b.second;
  double t = (ra*ra-rb*rb+d*d)/2/d, h = sqrt(ra*ra-t*t);
  P m = t/abs(b.first-a.first)*(b.first-a.first)+a.first;
  vector<P> cp(2,m);
  P n = (a.first-b.first)*P(0,1);
  n /= abs(n);
  cp[0] -= h*n;
  cp[1] += h*n;
  return cp;
}

vector<P> tangent_to_C(P p, C c){
  //点pから円cに伸ばした接線の接点を求める
  C c2 = C((p+c.first)/2.0,abs(p-c.first)/2.0);
  return cpcc(c,c2);
}

bool in_sector(P c, double r, double theta, double a, double b){
  if(abs(c) < r + EPS) return false;
  if(abs(c) + r > a + EPS) return false;
  vector<P> cps = tangent_to_C(P(0,0), C(c, r));
  if(cps.empty()) return false;
  P d = P(cos(b), sin(b));
  for(int i = 0; i < (int)cps.size(); ++i){
    P cp = cps[i];
    if(dot(cp, d)/abs(cp) < cos(theta/2) - EPS) return false;
  }
  return true;
}

void dfs(vector< vector<int> > &G, int v, vector<int> &P, vector<int> &R, int t){
  for(int i = 0; i < (int)G[v].size(); ++i){
    int v_ = G[v][i];
    int d = min(P[v_], R[v_]+t) - R[v_];
    R[v_] += d;
    //for(int i = 0; i < (int)R.size(); ++i) cout << R[i] << " ";cout << endl;
    if(d > 0) dfs(G, v_, P, R, d);
  }
}

int solve(vector< vector<int> > &G, vector<int> P){
  int n = G.size();
  vector<int> R(n, 0);
  R[0] = P[0];
  dfs(G, 0, P, R, R[0]);
  //for(int i = 0; i < n; ++i) cout << R[i] << " ";cout << endl;
  return R.back();
}

int main(){
  int N;
  cin >> N;
  double theta, a;
  vector<int> Power(N+2, 0);
  Power.back() = (int)1e9;
  cin >> theta >> a >> Power[0];
  theta *= pi/180.0;
  vector<P> L(N+1);
  vector<double> R(N+1), A(N), T(N), B(N);
  for(int i = 0; i < N; ++i){
    double x, y;
    cin >> x >> y >> R[i] >> T[i] >> A[i] >> B[i] >> Power[i+1];
    L[i] = P(x, y);
    T[i] *= pi/180.0;
    B[i] *= pi/180.0;
  }
  double x, y;
  cin >> x >> y >> R[N];
  L[N] = P(x, y);
  vector< vector<int> > G(N+2);
  for(int i = 0; i < N; ++i){
    for(int j = 0; j <= N; ++j){
      if(i == j) continue;
      if(in_sector(L[j]-L[i], R[j], T[i], A[i], B[i])){
        G[i+1].push_back(j+1);
        //cout << i << " " << j << endl;
      }
    }
  }

  int ans = 0;
  for(int i = 0; i <= N; ++i){
    if(abs(L[i]) + R[i] > a) continue;
    if(abs(L[i]) - R[i] < EPS) continue;
    vector<P> cps = tangent_to_C(P(0,0), C(L[i], R[i]));
    if(cps.empty()) continue;
    P cp = cps[0];
    if(arg(cps[0]) > arg(cps[1])) swap(cps[0], cps[1]);
    double b = arg(cp*P(cos(theta/2), sin(theta/2)));
    G[0] = vector<int>();
    for(int j = 0; j <= N; ++j){
      if(in_sector(L[j], R[j], theta, a, b)){
        G[0].push_back(j+1);
      }
    }
    /*
    cout << "i = " << i << endl;
    for(int j = 0; j < N+2; ++j){
      cout << j << " : ";
      for(int k = 0; k < (int)G[j].size(); ++k) cout << G[j][k] << " ";cout << endl;
    }
    cout << solve(G, Power) << endl;
    */
    ans = max(ans, solve(G, Power));
  }
  cout << ans << endl;
  return 0;
}


```