Problem: I'm traveling to a country with a rabbit. There are n cities in this country numbered from 1 to n, and the rabbit is now in city 1. City i is a point on the coordinate plane (xi, yi) ).

Rabbits travel to meet the following conditions.

* The travel path is a polygonal line, each part of which must be a line segment connecting two different cities.
* The total length of the travel route must be r or less. The overlapping part of the route is also counted for the number of times it has passed.
* When the direction of movement changes, the bending angle must be less than or equal to θ. There is no limit to the initial direction of movement.



If you move from one city to another, you will get one carrot in the destination city. You can visit the same city multiple times, and you will get a carrot each time you visit. Find the maximum number of carrots you can put in.



Input

One integer n is given on the first line of the input, and two real numbers r and θ are given on the second line, separated by a space.

1 ≤ n ≤ 20
0 <r <104
0 ° <θ <180 °


The following n lines are given the integers xi and yi separated by spaces.

-10 000 ≤ xi, yi ≤ 10 000

The answer does not change even if r and θ are changed within ± 10-3.
The locations of both cities are different.

Output

Output the maximum number of carrots that the rabbit can get on this trip in one line.

Example

Input

5
100.1 90.1
0 0
0 10
5 5
10 0
10 10


Output

10

Solution (in CPP):

Solution:
#include <iostream>
#include <complex>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 1e9
#define EPS 1e-6

typedef complex<double> Point;
typedef pair<Point, Point> Line;
double dis(Point a, Point b){ return abs(a - b); }
double dot(Point a, Point b){ return a.real() * b.real() + a.imag() * b.imag(); }

//テッツシツ津」ツ?、テ」ツ?ョテ」ツδ凖」ツつッテ」ツδ暗」ツδォABテ」ツ?ョテ」ツ?ェテ」ツ?凖ィツァツ津・ツコツヲテ篠クテ」ツつ津ヲツアツづ」ツつ?」ツつ?(テ」ツδ催」ツδε」ツδ暗」ツ?凝」ツつ嘉ヲツ仰セテ」ツ?」テ」ツ?ヲテ」ツ?催」ツ?淌」ツつづ」ツ?ョテ」ツ?ョテ、ツクツクテ」ツつウテ」ツδ?
double AngleOf2Point(Point A, Point B){
  //テ」ツδ凖」ツつッテ」ツδ暗」ツδォAテ」ツ?ィBテ」ツ?ョテゥツ閉キテ」ツ?陛」ツつ津ィツィツ暗ァツョツ療」ツ?療」ツ??
  //テ・ツ??ァツゥツ催」ツ?ィテ」ツδ凖」ツつッテ」ツδ暗」ツδォテゥツ閉キテ」ツ?陛」ツつ津、ツスツソテ」ツ?」テ」ツ?ヲcosテ篠クテ」ツつ津ヲツアツづ」ツつ?」ツつ?
  double length_A = abs(A);
  double length_B = abs(B);
  double cos_sita = dot(A, B) / (length_A * length_B );
  
  //cosテ篠クテ」ツ?凝」ツつ嘉篠クテ」ツつ津ヲツアツづ」ツつ?」ツ??テ」ツ??80テ」ツ?ョティツァツ津・ツコツヲテ」ツ?ォテ・ツ、ツ嘉ヲツ渉?
  double sita = acos( cos_sita );	
  sita = sita * 180.0 / M_PI;
  
  return sita;
}
double AngleOf2Line(Line A, Line B){ return AngleOf2Point(A.first - A.second, B.first - B.second); }


int main(void){
  int n;
  double r, theta;
  cin >> n >> r >> theta;

  int x, y;
  vector<Point> town;
  for(int i = 0; i < n; i++){
    cin >> x >> y;
    town.push_back(Point(x, y));
  }

  // adj[i][j]: jテ」ツ?凝」ツつ永テ」ツ?ォテ」ツ?催」ツ?淌・ツセツ古」ツ?ォテゥツ?キテァツァツサテ」ツ?ァテ」ツ?催」ツつ凝ゥツ?づァツつケテ」ツδェテ」ツつケテ」ツδ?
  vector<vector<vector<int> > > adj(n, vector<vector<int> >(n));
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      for(int k = 0; k < n; k++)
        if(i != j && i != k)
          if(AngleOf2Line(make_pair(town[j], town[i]), make_pair(town[i], town[k])) <= theta + EPS)
            adj[i][j].push_back(k);

  // dp[i][j][k]: jテ」ツ?凝」ツつ永テ」ツ?ォテヲツ敖・テ」ツ?淌ヲツ卍づァツつケテ」ツ?ァテ」ツδ凝」ツδウテ」ツつクテ」ツδウテ」ツつ談+1テヲツ慊ャGETテ」ツ?療」ツ?ヲテ」ツつ凝・ツ?エテ・ツ青暗」ツ?ョテヲツ慊?ァツ淞ュテァツオツ古ィツキツッ
  int int_r = (int)r + 1;
  vector<vector<vector<double> > > dp(n, vector<vector<double> >(n, vector<double>(int_r, INF)));
  for(int now = 1; now < n; now++){ dp[now][0][0] = dis(town[0], town[now]); }
  for(int carrot = 0; carrot < int_r - 1; carrot++){
    for(int now = 0; now < n; now++){
      for(int prev = 0; prev < n; prev++){
        for(size_t i = 0; i < adj[now][prev].size(); i++){
          int next = adj[now][prev][i];
          dp[next][now][carrot + 1] = min(dp[next][now][carrot + 1],
                                          dp[now][prev][carrot] + dis(town[now], town[next]));
        }
      }
    }
  }

  // テァツュツ氾」ツ?暗」ツつ津ィツィツ暗ァツョツ療」ツ?療」ツ?ヲテ・ツ?コテ・ツ環?
  int ans = -1;
  for(int carrot = 0; carrot < int_r; carrot++)
    for(int now = 0; now < n; now++)
      for(int prev = 0; prev < n; prev++)
        if(dp[now][prev][carrot] <= r + EPS)
          ans = carrot;
  
  cout << ans + 1 << endl;
  return 0;
}