Problem: One day Nikita found the string containing letters "a" and "b" only. 

Nikita thinks that string is beautiful if it can be cut into 3 strings (possibly empty) without changing the order of the letters, where the 1-st and the 3-rd one contain only letters "a" and the 2-nd contains only letters "b".

Nikita wants to make the string beautiful by removing some (possibly none) of its characters, but without changing their order. What is the maximum length of the string he can get?

Input

The first line contains a non-empty string of length not greater than 5 000 containing only lowercase English letters "a" and "b". 

Output

Print a single integer — the maximum possible size of beautiful string Nikita can get.

Examples

Input

abba


Output

4

Input

bab


Output

2

Note

It the first sample the string is already beautiful.

In the second sample he needs to delete one of "b" to make it beautiful.

Solution (in JAVA):

Solution:
import java.io.* ;
import java.util.* ;
import java.util.stream.* ;
import java.text.* ;
import java.math.* ;
public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		Solver Machine = new Solver() ;
		Machine.Solve() ;	
		Machine.Finish();
	}	
}
class Mod{
	static long mod=1000000007 ;
	static long d(long a,long b){ return (a*MI(b))%mod ; }
	static long m(long a , long b){ return (a*b)%mod ; }
	static private long MI(long a ){ return pow(a,mod-2) ; }
	static long pow(long a,long b){
		if(b<0) return pow(MI(a),-b) ;
		long val=a ; long ans=1 ;
		while(b!=0){
			if((b&1)==1) ans = (ans*val)%mod ; 
			val = (val*val)%mod ; 
			b>>=1 ;
		}
		return ans ;
	}	
}
class pair implements Comparable<pair>{
	long x ; long y ; 
	pair(long x,long y){ this.x=x ; this.y=y ;}
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
class Solver{	
	FasterScanner ip = new FasterScanner(System.in) ;	  
	PrintWriter op = new PrintWriter(System.out) ;
	void Solve() throws IOException{
		char c[] = ip.S().toCharArray() ;
		int n = c.length ;
		long pa[] = new long[n] ;
		pa[0] = c[0]=='a' ? 1 : 0 ;
		for(int i=1 ; i<n ; i++) pa[i] = pa[i-1]+(c[i]=='a' ? 1 : 0) ;
		long pb[] = new long[n] ;
		pb[0] = c[0]=='b' ? 1 : 0 ;
		for(int i=1 ; i<n ; i++) pb[i] = pb[i-1]+(c[i]=='b' ? 1 : 0) ;
		long ans = Long.MIN_VALUE ;
		for(int i=-1 ; i<n ; i++)
			for(int j=i ; j<n ; j++){
				long cut1 = (i==-1 ? 0 : pb[i]) ;
				long cut2 = (i==j ? 0 : (pa[j]-((i==-1) ? 0 : pa[i]))) ;
				long cut3 = (pb[n-1]-(j==-1 ? 0 : pb[j])) ;
				ans = Long.max(ans,n-(cut1+cut2+cut3)) ;
			}
		pln(ans) ;
	}
	void p(Object o){
		op.print(o) ;
	}
	void pln(Object o){
		op.println(o) ;
	}
	void pArr(String name,Object arr,char type){
		p(name+": [") ;
		if(type=='i'){ 
			int arr1[] = (int[]) arr ;
			for(int i=0 ; i<arr1.length ; i++) p(arr1[i]+(i+1==arr1.length ? "" : ",")) ;		 
		}else if(type=='l'){ 
			long arr1[] = (long[]) arr ;
			for(int i=0 ; i<arr1.length ; i++) p(arr1[i]+(i+1==arr1.length ? "" : ",")) ;
		}else if(type=='b'){
			boolean arr1[] = (boolean[]) arr ;
			for(int i=0 ; i<arr1.length ; i++) p((arr1[i] ? 1 : 0)+(i+1==arr1.length ? "" : ",")) ;
		}
		pln("]") ;
	}	
	void Finish(){
		op.flush();
		op.close();
	}	
}
@SuppressWarnings("serial")
class mylist extends ArrayList<Integer>{
}
@SuppressWarnings("serial")
class myset extends TreeSet<Long>{
 
}
@SuppressWarnings("serial")
class mystack extends Stack<Integer>{
}
@SuppressWarnings("serial")
class mymap extends TreeMap<Long,Integer>{
}
class FasterScanner { 
	private InputStream mIs;
	private byte[] buf = new byte[1024];
	private int curChar,numChars;
	public FasterScanner() { this(System.in); } 
	public FasterScanner(InputStream is) { mIs = is;} 
	public int read() {
		if (numChars == -1) throw new InputMismatchException();    
		if (curChar >= numChars) {
			curChar = 0;
			try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}
			if (numChars <= 0) return -1;            
		}
		return buf[curChar++];
	} 
	public String nextLine(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	} 
	public String S(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		}while (!isSpaceChar(c));
		return res.toString();
	} 
	public long l(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		int sgn = 1;
		if (c == '-') { sgn = -1 ; c = read() ; }
		long res = 0;
		do{
			if (c < '0' || c > '9') throw new InputMismatchException();
			res *= 10 ; res += c - '0' ; c = read();
		}while(!isSpaceChar(c));
		return res * sgn;
	} 
	public int i(){
		int c = read() ;
		while (isSpaceChar(c)) c = read();        
		int sgn = 1;
		if (c == '-') { sgn = -1 ; c = read() ; }
		int res = 0;
		do{
			if (c < '0' || c > '9') throw new InputMismatchException();
		res *= 10 ; res += c - '0' ; c = read() ;
		}while(!isSpaceChar(c));
		return res * sgn;
	} 
	public int[] ia(int n){
		int a[] = new int[n] ;
		for(int i=0 ; i<n ; i++) a[i] = i() ;
		return a ;
	}
	public long[] la(int n){
		long a[] = new long[n] ;
		for(int i=0 ; i<n ; i++) a[i] = l() ;
		return a ;
	}
	public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
	public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
}